中国剩余定理C++实现

笔者最近对中国剩余定理产生兴趣,遂以C++写为代码,在此记录一下。

1、中国剩余定理

中国剩余定理源于《孙子算经》,其具体在于解决以下形式方程:

{xa1(mod m1)xa2(mod m2)xa3(mod m3)...xan(mod mn)\begin{aligned}&\begin{cases}x\equiv a_1(mod~m_1)\\x\equiv a_2(mod~m_2)\\x\equiv a_3(mod~m_3)\\...\\x\equiv a_n(mod~m_n)\end{cases}\end{aligned}

核心公式为:

K=j=1nmj,x=[i=1nai×Kmi×(Kmi)1(modmi)]modK\begin{aligned}K=\prod_{j=1}^{n}m_{j},\quad x=\left[\sum_{i=1}^{n}a_{i}\times\frac{K}{m_{i}}\times(\frac{K}{m_{i}})^{-1}(modm_{i})\right]modK\end{aligned}

2、C++代码实现

要实现以上公式 ,需要两部分,一是算出公式中乘法逆元部分,二是完成公式主体部分计算。
乘法逆元部分使用扩展欧几里得算法,代码如下:

1
int ex_gcd(int a, int b, int &x, int &y) //扩展欧几里得 { if (!b) { x = 1; y = 0; return a; } int r = ex_gcd(b, a%b, x, y); int t = x; x = y; y = t - a / b * y; return r; } int mod_reverse(int a, int n)//ax=1(mod n) 求a的逆元x { int d, x, y; d = ex_gcd(a, n, x, y); if (d == 1) return (x%n + n) % n; else return -1; }

公式主体部分:其中输入以CH_Remainder结构体储存,格式为{2,3}(模3余2)

1
typedef struct CH_Remainder { int result, mod_num; }CH_Remainder,ch_remainder[100]; int Ch_remainder_theorem(ch_remainder a )//主体部分 { int k=a[0].mod_num; int b = 0, z = 0; for (int i = 1; a[i].mod_num; i++) { k *= a[i].mod_num; } for (int i = 0; a[i].mod_num; i++) { z = mod_reverse(k / a[i].mod_num, a[i].mod_num);//乘法逆元 if (z==-1) return -1; b += (a[i].result*(k / a[i].mod_num)*z); } return b % k; }

3、具体使用
以经典的“物不知数”问题为例,其正文为:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
主函数调用如下:

1
int main() { ch_remainder a = { {2,3},{3,5},{2,7} }; cout <<Ch_remainder_theorem(a) << endl; }

转载自这里