中國剩余定理

孫子算經(jīng)里有這樣一個問題：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？”

翻譯成現(xiàn)在的數(shù)學(xué)問題就是?x%3 == 2，x%5 == 3，x%7 ==? 2,求x?的值；

遇到這這樣一個問題很多C語言初學(xué)者不禁會想到用暴力可以算出來，還要這樣一個定理干嘛？

如果數(shù)據(jù)相當大呢？計算機就會計算相當困難。然而這個問題早早的就被孫子解決了。

?求出3,5,7?兩兩中的最小公倍數(shù)lcm，k*lcm與另一個數(shù)mod等于1(找出一個符合條件的k）；

??用k*lcm*另一個沒有在lcm中的數(shù)的等式的余數(shù)??[（有點繞）就是?lcm(3,5),另一個數(shù)就是7?在x%7==2?的等式中的余數(shù)?就是2?即找出這k*lcm（3,5）*2]

求法(剩余定理思想)：

??Lcm(3,5)?=?15;???//?lcm是最小公倍數(shù)?

??Lcm(3,7)?=?21;

??Lcm(5,7)?=?35;

??a*15%7?==?1;

??b*21%5?==?1;

??c*35%3?==?1;

??可求得a,b,c的值為1,1,2;

??我們可得15%7?==?1?,?21%5?==?1?,?70%3?==?1；

??Ans?=?(15*2?+?21*3?+?70*2)?%?lcm(3,5,7);??

??Ans?=?23;

再加一個例題：

一個數(shù)被3除余1，被4除余2，被5除余4，這個數(shù)最小是幾？

?題中3、4、5三個數(shù)兩兩互質(zhì)。?則〔4，5〕=20；〔3，5〕=15；〔3，4〕=12；〔3，4，5〕=60。?

為了使20被3除余1，用20×2=40；?使15被4除余1，用15×3=45；?使12被5除余1，用12×3=36。?

然后，40×1＋45×2＋36×4=274，?

因為，274>60；

所以，274%60?=?34，就是所求的數(shù)。

?

粘個剩余定理題????POJ?1006?http://poj.org/problem?id=1006

題目又上角有中文意思

?

這道題的解法就是：?

已知(ans+d)%23=a;? ?(ans+d)%28=b;? ?(ans+d)%33=c?
???????使33×28×X被23除余1，用33×28×8 = 5544；?
???????使23×33×Y被28除余1，用23×33×19 = 14421；?
???????使23×28×Z被33除余1，用23×28×2 = 1288。

? ? ? 于是X==8, Y==19, Z==2;?
??????因此有（5544×a + 14421×b + 1288×c）% lcm(23,28,33) =ans + d?

又23、28、33互質(zhì)，即lcm(23,28,33) = 21252;
??????所以有ans =（5544×a+14421×b+1288×c-d）% 21252

AC代碼

#include<iostream> #include<stdio.h> using namespace std; int main() { int a, b, c, d,cnt=1; int ans; while (scanf("%d%d%d%d", &a, &b, &c, &d)!=EOF&&a!=-1) { ans = (a * 5544 + b * 14421 + c * 1288) % 21252; ans -= d; if (ans<=0) ans += 21252; if(ans>21252) ans=21252; printf("Case %d: the next triple peak occurs in %d days.\n", cnt++, ans); } return 0; }

這個題暴力也能過

暴力AC代碼

#include<iostream> #include<stdio.h> using namespace std; int main() { int a, b, c, d,cnt=1,i; while (scanf("%d%d%d%d", &a, &b, &c, &d)!=EOF&&a!=-1) { for(i=1; ; i++) if((i-a)%23==0&&(i-b)%28==0&&(i-c)%33==0&&i>d) { break; } printf("Case %d: the next triple peak occurs in %d days.\n", cnt++, i-d); } return 0; }

?

總結(jié)

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

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