典型的中國余數(shù)定理的應用。 設(shè)m1,m2,..,mk是k個兩兩互素的正整數(shù)，m=m1*m2*...*mk，Mi=m/mi(i=1,2,..,k)。則同余方程組 x≡b1(mod m1) x≡b2(mod m2） ...... x≡bk(mod mk) 有唯一解。 x≡M'1M1b1＋…＋M'kMkbk （modm），其中M'iMi≡1 （modmi），i＝1，2，…，k? 舉個最經(jīng)典的例子，今有物不知其數(shù)，三三數(shù)之余二 ，五五數(shù)之余三 ，七七數(shù)之余二，問物幾何？ 除數(shù)序列{3,5,7}；對應的余數(shù)序列{2,3,2} 接下來我們需要求一個數(shù)k1滿足k1 %3==1&&k1%5==k1%7==0。 因為k1%5==k1%7==0，所以又k1=35的倍數(shù)，得k最小應該為70。 類推得k2=21，k3=15, 此時70a+21b+15c就是mod 3余a,mod 5余b,mod 7余c的數(shù)了。 為什么一直要求除數(shù)序列要互素？原因是如果不互素的話那么肯定無法求出全部的滿足如上定理的k，結(jié)論自然也無法求得。 解題的關(guān)鍵就是求ki。 #include <stdio.h> int main() { int p,e,i,d,a,t=0;while(1){scanf("%d%d%d%d",&p,&e,&i,&d);if(p==-1 && e==-1 && i==-1 && d==-1)break;a=(5544*p+14421*e+1288*i-d+21252)%21252;if(!a)//a==0a=21252;printf("Case %d: the next triple peak occurs in %d days.\n",++t,a);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/acsmile/archive/2011/05/10/2042093.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1006的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。