問題簡(jiǎn)單來說就是 a = ai (mod ni)   求未知數(shù)a,
 以下小結(jié)略去證明, 只是對(duì)定理作了必要的解釋, 要了解相關(guān)定理,可查閱數(shù)論資料.

中國(guó)余數(shù)定理:
      設(shè) n=n1*n2...nk, 其中因子兩兩互質(zhì).有:  a-----(a1,a2,...,ak), 其中ai = a mod ni, 則 a和(a1,a2,...,ak)關(guān)系是一一對(duì)應(yīng)的.就是說可以由 a求出(a1,a2,...,ak), 也可以由(a1,a2,...,ak)求出a

推論1:
      對(duì)于 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很大時(shí))

中國(guó)剩余定理關(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;
}

int main() {
    a[0] = 4; a[1] = 5;
    n[0] = 5; n[1] = 11;
    nn = 2;
    printf("%d\n", lmes());
    return 0;
}