且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

poj1006生理周期(中国剩余定理)

更新时间:2022-09-22 12:21:46

 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==1
21    //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 } 









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3885714.html,如需转载请自行联系原作者