poj1006生理周期（中国剩余定理）

1 /* 2 中国剩余定理可以描述为： 3 若某数x分别被d1、、…、dn除得的余数为r1、r2、…、rn，则可表示为下式： 4 x=R1r1+R2r2+…+Rnrn+RD 5 其中R1是d2、d3、…、dn的公倍数，而且被d1除，余数为1；（称为R1相对于d1的数论倒数） 6 R1 、 7 R2 、 8 … 、 9 Rn是d1、d2、…、dn-1的公倍数，而且被dn除，余数为1；10 D是d1、d2、…、的最小公倍数；11 R是任意整数（代表倍数），可根据实际需要决定；12 且d1、、…、必须互质，以保证每个Ri(i=1,2，…，n)都能求得.13 */14 #include<iostream>15 using namespace std;16 int main(){17 int a, b, c, d;18 int cnt=0;19 int x23=5544, x13=14421, x12=1288, x=21252;20 //x23为b,c的公倍数， 且x23%==1 x23为a,c的公倍数， 且x23%==1 x13为a,b的公倍数， 且x12%c==121 //a, b, c 为余数 22 while(cin>>a>>b>>c>>d && a!=-1){23 int res=(a*x23 + b*x13 + c*x12) % x;24 res-=d;25 if(res<=0)26 res=(res+x-1)%x+1;27 cout<<"Case "<<++cnt<<": the next triple peak occurs in "<<res<<" days."<<endl;28 } 29 return 0;30 }