hdu 1370 Biorhythms 中国剩余定理的应用

BiorhythmsTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1050 Accepted Submission(s): 455


Problem DescriptionInputOutputSample InputSample OutputSource#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,c,d,C=1,ans;int w[15]={23,28,33},a[15];scanf("%d",&c);while (scanf("%d %d %d %d",&a[0],&a[1],&a[2],&d)!=EOF) {if(a[1]==-1&&a[2]==-1&&a[0]==-1) break;a[0]%=23;a[1]%=28;a[2]%=33;ans=Chinese_Remainder(a,w,3); ans=ans-d;if(ans<=0) ans=ans+21252;printf("Case %d: the next triple peak occurs in %d days.\n", C++,ans); }return 0;}