poj1006生理周期

参考资料 http://wenku.baidu.com/link?url=Bbd0xMskWTglq9lAO0iG4BiU1zudR88Fl2YREZXIIV5kIanht9fu4Fbff-1ccpbLl0pXTeWCkeL–VGG4mFa2Hp_mubW1ylIaTBzDxLyiwa 这篇文章介绍扩展欧几里得算法http://972169909-qq-com.iteye.com/blog/1125532 这篇文章讲到同余加性和乘性 #include<vector> #include<iostream> using namespace std; int arr[3]={23,28,33}; int gcd(int a,int b,int& x,int& y){ if(b==0) { x=1;y=0; return a; } int q=gcd(b,a%b,x,y); int temp=x; x=y; y=-(y*a/b-temp); return q; } int main() { int x,y,m=28*23*33; vector<int* > vrr; while(1) { int* v=new int[4]; for (int i = 0; i < 4; ++i) { cin>>v[i]; } int count=0; for (int i = 0; i < 4; ++i) { if(v[i]==-1) count++; } if(count==4) break; vrr.push_back(v); } for (int j = 0; j < vrr.size(); ++j) { int res=0; for (int i = 0; i < 3; ++i) { gcd(m/arr[i],arr[i],x,y); res+=m/arr[i]*x*vrr[j][i]; } res=res%21252; while(res<=0) res+=21252; cout<<"Case "<<j+1<<": the next triple peak occurs in "<<res-vrr[j][3]<<" days."<<endl; } return 0; } /* Sample Input 0 0 0 0 0 0 0 100 5 20 34 325 4 5 6 7 283 102 23 320 203 301 203 40 -1 -1 -1 -1 Sample Output Case 1: the next triple peak occurs in 21252 days. Case 2: the next triple peak occurs in 21152 days. Case 3: the next triple peak occurs in 19575 days. Case 4: the next triple peak occurs in 16994 days. Case 5: the next triple peak occurs in 8910 days. Case 6: the next triple peak occurs in 10789 days. */