本文主要是介绍51Nod_1079 中国剩余定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
51Nod_1079 中国剩余定理
http://www.51nod.com/Challenge/Problem.html#!#problemId=1079
题目
一个正整数K，给出K Mod 一些质数的结果，求符合条件的最小的K。例如，K % 2 = 1, K % 3 = 2, K % 5 = 3。符合条件的最小的K = 23。
输入
第1行：1个数N表示后面输入的质数及模的数量。（2 <= N <= 10)；第2 - N + 1行，每行2个数P和M，中间用空格分隔，P是质数，M是K % P的结果。（2 <= P <= 100, 0 <= K < P)
输出
输出符合条件的最小的K。数据中所有K均小于10^9。
样例输入
3
2 1
3 2
5 3样例输出
23
分析
中国剩余定理。例如，K % 2 = 1, K % 3 = 2, K % 5 = 3。符合条件的最小的K = 23。通过中国剩余定理如何求解？实际上很简单，先求出满足第一个等式最小的K，即K=3，然后每次加2（这样保证满足第一个式子），直到满足第二个式子，即K=5，然后每次加上2和3的最小公倍数6（这样保证满足前两个式子），直到满足第三个式子，即K=23。通过这个小例子就可以看到中国剩余定理就是保证已经考察过的等式始终成立（每次递增它们的最小公倍数），然后不断满足为成立的式子
C语言程序
#include<stdio.h>struct PM{int p,m;
}a[10];int main()
{int n,p,m,i;scanf("%d",&n);for(i=0;i<n;i++)scanf("%d%d",&a[i].p,&a[i].m);int s=1,ans=a[0].m;for(i=0;i<n-1;i++){s=s*a[i].p;//s是考察过的质数的最小公倍数 while(ans%a[i+1].p!=a[i+1].m)ans+=s;}printf("%d\n",ans);return 0;
}
这篇关于51Nod_1079 中国剩余定理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
