中國餘數定理

典故：http://www.edp.ust.hk/previous/math/history/5/5_4/5_4_5.htm。

聯立同餘方程式
x ≡ r1 (mod m1)
x ≡ r2 (mod m2)
...
x ≡ rk (mod mk)
其中 m1 , m2 , ... , mk 兩兩皆互質

令
M = m1 * m2 * ... * mk
M1 = M/m1
M2 = M/m2
...
Mk = M/mk

再找出 pk、qk 使得 Mk*pk + mk*qk = 1

可發現
(Mi*pi) % mj = 1 when i = j
(Mi*pi) % mj = 0 when i ≠ j

原聯立同餘方程式的解為
x ≡ r1*M1*p1 + r2*M2*p2 + ... + rk*Mk*pk (mod M)

程式碼實作相當簡單，時間複雜度為O(KlogM)，為K次輾轉相除法的時間，其中M為最大的模數。

/* Extended Euclid's Algorithm, n * u ≡ 1 (mod m) */ int inverse(int n, int m) { int d = m, u = 0, s = 1, q, r, t; while (n != 0) { q = d / n, r = d % n; d = n, n = r; t = u - q * s, u = s, s = t; } if (u < 0) u += m; return u; } /* Chinese Remainder Theorem */ int CRT(int r[], int m[], int K) { int M = 1, n = 0; for (int i=0; i<K; ++i) M *= m[i]; for (int i=0; i<K; ++i) (v += r[i] * M/m[i] * inverse(M/m[i], m[i])) %= M; if (n < 0) n += M; return n; }

UVa 756 700