中国剩余定理 模板
http://blog.csdn.net/xiaotaoqibao/article/details/5781131
参考网址
一个小知识点 也记下来
如果整数 a 除以整数 b 的余数是 1，那么 a 的 2 倍，3 倍，4 倍……b-1 倍除以 b 的余数
分别是 1*1，2*1，3*1，4*1，......和(b-1)*1。
例如：15÷7=2……余1，那么：
2*15÷7=4……余 2 (=2*1)
3*15÷7=6……余 3 (=3*1)
4*15÷7=8……余 4 (=4*1)
……
6*15÷7=12……余 6 (=6*1)
#include <iostream>using namespace std;int Extended_Euclid(int a,int b,int &x,int &y) //扩展欧几里得算法{int d;if(b==0){x=1;y=0;return a;}d=Extended_Euclid(b,a%b,y,x);y-=a/b*x;return d;}int Chinese_Remainder(int a[],int w[],int len) //中国剩余定理 a[]存放余数 w[]存放两两互质的数{int i,d,x,y,m,n,ret;ret=0;n=1;for (i=0;i<len;i++)n*=w[i];for (i=0;i<len;i++){m=n/w[i];d=Extended_Euclid(w[i],m,x,y);ret=(ret+y*m*a[i])%n;}return (n+ret%n)%n;}int main(){int n,i;int w[15],b[15];while (scanf("%d",&n),n) {for (i=0;i<n;i++){scanf("%d%d",&w[i],&b[i]);}printf("%d/n",Chinese_Remainder(b,w,n));}return 0;}