中国剩余定理(也叫孙子定理)
今儿偶尔无聊，看到一个叫做“中国剩余定理”的玩意，觉得煞是好玩，便写一点总结上题目先，
假设一个数（1）被3除余2，（2）被5除余4，（3）被7除余6，求满足条件的最小整数
lcm(5, 7) 为35 35*2=70刚好除以3余数为1
lcm(3, 7) 为21 21*1=21刚好除以5余1
lcm(5, 3) 为15 15*1 = 15刚好除以7余1
接下来(70*2 +21*4 +15*6)%lcm(70, 21, 15) = 104
最终，104就是要求的结果。
下面，写成数学公式
题目：假设一个数M分别被A, B, C相除余数为a,b, c，求满足条件的最小整数(A, B, C, a, b, c均为正整数)
步骤1： 先求解LCM(B, C) = A' 给A'乘上适当的正整数Ka(从1开始递增), A'*Ka%A = 1一旦成立就终止，令A'' = A'*Ka同理可求B'', C''定义同上
步骤2：求解LCM(A, B, C)
结果： 那么最后结果可以表示为(A'' * a + B'' * b + C" * c)%LCM(A, B, C);
下面，用C++实现完整代码
[cpp]
#include <iostream>
using namespace std;
int 易做图(int a, int b) {
int tmp;
if (a < b)
return 易做图(b, a);
while (b) {
tmp = b;
b = a % b;
a = tmp;
}
return a;
}
int LCM(int a, int b) {
return a*b/易做图(a, b);
}
void GET2(int& K2, int K) {
int i = 1;
while (1) {
if (K2 % K == 1)
break;
else
K2 *= ++i;
}
}
int main() {
int A, A1, A2, B, B1, B2, C, C1, C2, a, b, c, i, D;
cout << "分别输入三个除数和余数: ";
cin >> A >> a;
cin >> B >> b;
cin >> C >> c;
//求解最小公倍数A', B', C'
A2 = A1 = LCM(B, C);
B2 = B1 = LCM(A, C);
C2 = C1 = LCM(A, B);
D = LCM(A1, A); //三个数的最小公倍数
//求解A'', B'', C''
GET2(A2, A);
GET2(B2, B);
GET2(C2, C);
cout << "要求的数为: " << (A2 * a + B2 * b + C2 * c) % D << endl;
return 0;
}
补充：软件开发 , C++ ,
