|
例1：一個數(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，
因?yàn)椋?/span>274>60，所以，274－60×4=34，就是所求的數(shù)。
例2：一個數(shù)被3除余2，被7除余4，被8除余5，這個數(shù)最小是幾？
題中3、7、8三個數(shù)兩兩互質(zhì)。
則〔7，8〕=56；〔3，8〕=24；〔3，7〕=21；〔3，7，8〕=168。
為了使56被3除余1，用56×2=112；
使24被7除余1，用24×5=120。
使21被8除余1，用21×5=105；
然后，112×2＋120×4＋105×5=1229，
因?yàn)椋?/span>1229>168，所以，1229－168×7=53，就是所求的數(shù)。
例3：一個數(shù)除以5余4，除以8余3，除以11余2，求滿足條件的最小的自然數(shù)。
題中5、8、11三個數(shù)兩兩互質(zhì)。
則〔8，11〕=88；〔5，11〕=55；〔5，8〕=40；〔5，8，11〕=440。
為了使88被5除余1，用88×2=176；
使55被8除余1，用55×7=385；
使40被11除余1，用40×8=320。
然后，176×4＋385×3＋320×2=2499，
因?yàn)椋?/span>2499>440，所以，2499－440×5=299，就是所求的數(shù)。
例4：有一個年級的同學(xué)，每9人一排多5人，每7人一排多1人，每5人一排多2人，問這個年級至少有多少人 ？（幸福123老師問的題目）
題中9、7、5三個數(shù)兩兩互質(zhì)。
則〔7，5〕=35；〔9，5〕=45；〔9，7〕=63；〔9，7，5〕=315。
為了使35被9除余1，用35×8=280；
使45被7除余1，用45×5=225；
使63被5除余1，用63×2=126。
然后，280×5＋225×1＋126×2=1877，
因?yàn)椋?/span>1877>315，所以，1877－315×5=302，就是所求的數(shù)。
例5：有一個年級的同學(xué)，每9人一排多6人，每7人一排多2人，每5人一排多3人，問這個年級至少有多少人 ？（澤林老師的題目）
題中9、7、5三個數(shù)兩兩互質(zhì)。
則〔7，5〕=35；〔9，5〕=45；〔9，7〕=63；〔9，7，5〕=315。
為了使35被9除余1，用35×8=280；
使45被7除余1，用45×5=225；
使63被5除余1，用63×2=126。
然后，280×6＋225×2＋126×3=2508，
因?yàn)椋?/span>2508>315，所以，2508－315×7=303，就是所求的數(shù)。
（例5與例4的除數(shù)相同，那么各個余數(shù)要乘的“數(shù)”也分別相同，所不同的就是最后兩步。）
|
|
先寫出一個兩位數(shù)62，接著在62右端寫這兩個數(shù)字的和為8，得到628，再寫末兩位數(shù)字2和8的和10，得到62810，用上述方法得到一個有2006位的整數(shù)：628101123……，則這個整數(shù)的數(shù)字之和是（ ）。
（2006-5）÷10=200....1
17+35*200+1=7018
前面的62810數(shù)字和為17
后面開始，以“1123581347”為循環(huán)節(jié)
共循環(huán)10次，每次的和為35
最后余1，就加上1
所以結(jié)果是17+35*200+1=7018
例子：PKU 1006
因?yàn)橹挥腥齻€數(shù)23 28 33 且三個數(shù)兩兩互為質(zhì)數(shù)，所以“中國剩余定理”可知
對于每一組輸入數(shù)據(jù)p, e ,i, d，所求結(jié)果為：n = (R1*p + R2*e + R3*i)%21252-d
其中 R1%p=1, R2%e=1, R3%i=1;
R1 = 5544 = 28*33* 6; //28 33 的公倍數(shù)中能被23除余1的最小整數(shù)
R2 = 14221 = 23*33*19; //23 33 的公倍數(shù)中能被28除余1的最小整數(shù)
R3 = 1288 = 23*28* 2; //23 28 的公倍數(shù)中能被33除余1的最小整數(shù)
為了保證結(jié)果大于等于1且小于等于21252，結(jié)果修正為：n = (R1*p + R2*e + R3*i - d + 21252)%21252，并且如果n為0，則n = 21252為所求。
問題簡單來說就是 a = ai (mod ni) 求未知數(shù)a,
以下小結(jié)略去證明, 只是對定理作了必要的解釋, 要了解相關(guān)定理,可查閱數(shù)論資料.
中國余數(shù)定理:
設(shè)
n=n1*n2...nk, 其中因子兩兩互質(zhì).有: a-----(a1,a2,...,ak), 其中ai = a mod ni, 則
a和(a1,a2,...,ak)關(guān)系是一一對應(yīng)的.就是說可以由 a求出(a1,a2,...,ak), 也可以由(a1,a2,...,ak)求出a
推論1:
對于 a=ai (mod ni) 的同余方程,有唯一解
下面說說由(a1, a2, ..., ak)求a的方法:
定義 mi = n1*n2*...nk / ni; ci = mi(mf mod ni); 其中 mi*mf mod ni = 1;
則 a = (a1*c1+a2*c2+...+ak*ck) (mod n) (注:由此等式可求a%n, 當(dāng)n很大時)
中國剩余定理關(guān)鍵是mf的求法,如果理解了擴(kuò)展歐幾里得 ax+by=d, 就可以想到:
mi*mf mod ni = 1 => mi*mf+ni*y=1;
代碼如下:
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 100;
int nn, a[MAXN], n[MAXN];
int egcd(int a, int b, int &x, int &y) {
int d;
if (b == 0) {
x = 1; y = 0;
return a;
} else {
d = egcd(b, a%b, y, x);
y -= a/b*x;
return d;
}
}
int lmes() {
int i, tm=1, mf, y, ret=0, m;
for (i=0; i<nn; i++) tm *= n[i];
for (i=0; i<nn; i++) {
m = tm/n[i];
egcd(m, n[i], mf, y);
ret += (a[i]*m*(mf%n[i]))%tm;
}
return (ret+tm)%tm;
}