Chinese Remainder Theorem

中國餘數定理

典故: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為最大的模數。

UVa 756 700