POJ 1006 Biorhythms 中国剩余定理

定理"/>

POJ 1006 Biorhythms 中国剩余定理

#include <iostream>
using namespace std;
int p,e,i,d,A[3];
const int m[]={23,28,33},M=23*28*33;
void exgcd(int a,int b,int& x,int& y){if(b==0){x=1;y=0;}else{exgcd(b,a%b,y,x);y-=x*(a/b);}
}
int main(){///problem: find n satisfying (n+d)%23===p, (n+d)%28=i, (n+d)%33=eint t=1;while(cin>>p>>e>>i>>d){if(p==-1&&e==-1&&i==-1&&d==-1) break;int ans=0;A[0]=p,A[1]=e,A[2]=i;for(int k=0;k<3;k++){int x,y,Mi=M/m[k];exgcd(Mi,m[k],x,y);ans=(ans+A[k]*Mi*x)%M;}if(ans<=d) ans+=M;cout<<"Case "<<t++<<": the next triple peak occurs in "<<ans-d<<" days."<<endl;}return 0;
}