問題簡單來說就是 a = ai (mod ni) 求未知數a,
以下小結略去證明, 只是對定理作了必要的解釋, 要了解相關定理,可查閱數論資料.
中國余數定理:
設 n=n1*n2...nk, 其中因子兩兩互質.有: a-----(a1,a2,...,ak), 其中ai = a mod ni, 則 a和(a1,a2,...,ak)關系是一一對應的.就是說可以由 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, 當n很大時)
中國剩余定理關鍵是mf的求法,如果理解了擴展歐幾里得 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;
}
int main() {
a[0] = 4; a[1] = 5;
n[0] = 5; n[1] = 11;
nn = 2;
printf("%d\n", lmes());
return 0;
}
posted on 2007-08-27 16:46
豪 閱讀(11661)
評論(2) 編輯 收藏 引用 所屬分類:
算法&ACM