首页 > 代码库 > poj 1006 中国剩余定理
poj 1006 中国剩余定理
中国剩余定理出自《孙子算经》中的一个问题：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
这道题实际上就是解这么一个同余方程组：
x≡2 (mod 3)
x≡3 (mod 5)
x≡2 (mod 7) 求解x
至于该方程的解法，wikipedia上解释得很详细：
//Reference：http://blog.csdn.net/cyendra/article/details/38402869
eg：POJ 1006
其实画个图就明白了，
该问题就是求同余方程组的解：
n+d≡p (mod 23)
n+d≡e (mod 28)
n+d≡i (mod 33)
1 #include "iostream" 2 using namespace std; 3 int a[5],m[5]; 4 int p,e,i,d,ans; 5 6 int extend_gcd(int a,int b,int &x,int &y){ 7 if (b==0){ 8 x=1;y=0; 9 return a;10 }11 else{12 int r=extend_gcd(b,a%b,y,x);13 y=y-x*(a/b);14 return r;15 }16 }17 18 int CRT(int a[],int m[],int n)19 {20 int M=1;21 for (int i=1;i<=n;i++) M*=m[i];22 int ret=0;23 for (int i=1;i<=n;i++)24 {25 int x,y;26 int tm=M/m[i];27 extend_gcd(tm,m[i],x,y);28 ret=(ret+tm*x*a[i])%M;29 }30 return (ret+M)%M;31 }32 33 int main()34 {35 int T=0;36 while (cin>>p>>e>>i>>d)37 {38 T++;39 if ((p==-1)&&(e==-1)&&(i==-1)&&(d==-1))40 break;41 a[1]=p; a[2]=e; a[3]=i;42 m[1]=23; m[2]=28; m[3]=33;43 ans=CRT(a,m,3);44 ans=ans-d;45 if (ans<0) ans+=21252;46 ans=ans%21252;47 if (ans==0) ans=21252;48 //Case 1: the next triple peak occurs in 1234 days.49 cout<<"Case "<<T<<": the next triple peak occurs in "<<ans<<" days."<<endl;50 }51 return 0;52 }
poj 1006 中国剩余定理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。