本文主要是介绍中国剩余定理算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国剩余定理。
中国剩余定理的结论：
令任意固定整数为M，当M/A余a，M/B余b，M/C余c，M/D余d，…，M/Z余z时，这里的A，B，C，D，…，Z为除数，除数为任意自然数（如果为0，没有任何意义，如果为1，在孙子定理中没有计算和探讨的价值，所以，不包括0和1）时；余数a，b，c，d，……，z为自然整数时。
1、当命题正确时，在这些除数的最小公倍数内有解，有唯一的解，每一个最小公倍数内都有唯一的解；当命题错误时，在整个自然数范围内都无解。
2、当M在两个或两个以上的除数的最小公倍数内时，这两个或两个以上的除数和余数可以定位M在最小公倍数内的具体位置，也就是M的大小。
3、正确的命题，指没有矛盾的命题：分别除以A，B，C，D，…，Z不同的余数组合个数=A，B，C，D，…，Z的最小公倍数=不同的余数组合的循环周期．
注释：三数为a b c，余数分别为 m1 m2 m3.
⒈分别找出能被两个数整除，而满足被第三个整除余一的最小的数。(即k1，k2，k3)
k1%b==k1%c==0 && k1%a==1;
k2%a==k2%c==0 && k2%b==1;
k3%a==k3%b==0 && k3%c==1;
⒉将三个数（能被两个数整除、除以第三个数余1）乘对应数字的余数再加起来，减去这三个数的最小公倍数即得结果。
Answer = k1×m1 + k2×m2 + k3×m3 - P×（a×b×c);
P为满足Answer > 0的最大整数；
或者 Answer = (k1×m1 + k2×m2 + k3×m3）%(a×b×c) ;
代码实现如下：
void Getva()
{int i;for(i=1,r1=28*33;;i++)if(r1*i%23==1)break;r1*=i;for(i=1,r2=23*33;;i++)if(r2*i%28==1)break;r2*=i;for(i=1,r3=23*28;;i++)if(r3*i%33==1)break;r3*=i;
}
定理的解题思路：
令某数为M，令素数为A，B，C，D，…，Z，已知M/A余a，M/B余b，M/C余c，M/D余d，…，M/Z余z。求M=？
因为A，B，C，D，…，Z为不同的素数，故，B*C*D*…*Z不可能被A整除，有等差数列（B*C*D*…*Z）+（B*C*D*…*Z）N中取A个连续项，这A个连续项分别除以A的余数必然存在0，1，2，3，…，A-1，所以，从这A个连续项中能寻找到除以A余1的数。再用除以A余1的这个数*a其积必然除以A余a，这个除以A余a的数，为能够被素数B*C*D*…*Z整除的数，为第一个数；
再按同样的道理，从A*C*D*…*Z的倍数中寻找除以B余b的数，该数具备被素数A，C，D，…，Z整除的特性，为第二个数；
因为，第一个数除以A余a，第二个数能被素数A，C，D，…，Z整除，即能被A整除，所以，第一个数+第二个数之和，仍然保持除以A余a；
同理，第二个数除以B余b，因第一个数能被B整除，所以，第二个数+第一个数之和，仍然保持除以B余b。即，第一个数+第二个数之和，为满足除以A余a，除以B余b。
依此类推，按上面的方法寻找到除以各素因子的余数的数之总和，为满足除以各素因子余数的条件的数。总和再减去能被这几个素数共同整除的数（A*B*C*D*…*Z）N后，其差仍然保持除以各素因子余数的条件的数。由此构成孙子定理的解法。
证明
令T1=k1×m1,T2=k2×m2,T3=k3×m3;
因为 k1%a==1 ；所以 T1%a==m1;
对于 a，已知：T2%a==0,T3%a==0,T1%a==m1;
所以：Answer%a==m1;
因为：T1%b==0,T3%b==0,T2%b==m2 => Answer%b==m2
同理：Answer%c==m3;
又因为 a×b×c能同时整除 a b c，所以Answer ± P×（a×b×c）也是题目的解；
所以Answer是题目的解，又Answer = Answer % (a×b×c），所以Answer为最小解.
本题全代码：
<pre name="code" class="cpp">#include <stdio.h>
#include <string.h>
int r1,r2,r3,r;
void Getva()
{int i;for(i=1,r1=28*33;;i++)if(r1*i%23==1)break;r1*=i;for(i=1,r2=23*33;;i++)if(r2*i%28==1)break;r2*=i;for(i=1,r3=23*28;;i++)if(r3*i%33==1)break;r3*=i;
}int main()
{int p,e,i,d,sum,k=1;r=21252;Getva();while(scanf("%d%d%d%d",&p,&e,&i,&d)!=EOF && p!=-1){sum=(r1*p+r2*e+r3*i-d)%r;if(sum<=0) // 该步保证像第一个这样的特殊样例能过sum=(sum+r-1)%r+1; printf("Case %d: the next triple peak occurs in %d days.\n",k++,sum);}return 0;
}这篇关于中国剩余定理算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
