2. 中國剩餘定理

2021-06-12 23:19:43 +0800 CST Tags: c.r.t, m.m.i, number-theory

問題：給你一連串的 $x\equiv r_i$ (mod $m_i$)，其中 $m_i$ 們兩兩互質，且 $0\le r_i\lt m_i$，請找出滿足方程組的最小非負整數 $x_0$。

解法：其實這個題型如果要用程式去解的話可以不用中國剩餘定理的理論，我們只要每次合併其中兩個式子並找到其中的通解，再和其他剩下的式子做一樣的事，最後就能找到整體的通解。方法如下，對於兩條方程式 $x\equiv r_1$ (mod $m_1$) 和 $x\equiv r_2$ (mod $m_2$)，我們可以先把第一式替換成 $x = m_1 \cdot t + r_1$，並將其代入第二條方程式並得到 $m_1 \cdot t \equiv r_2 - r_1 \equiv r$ (mod $m_2$)，其中 $r\ge0$，又在上一節我們已經會求出滿足方程式 $m_1\cdot t' \equiv 1$ (mod $m_2$) 的最小正整數 $t':=t_0$，那一個合法的非負整數 $t$ 便是 $t_0\cdot r$，再代回去 $x$ 的原式便找到了一個整數 $x:=m_1\cdot t_0\cdot r + r_1$ 同時滿足那兩條方程式，又我們知道欲滿足第一式的整數會是每 $m_1$ 一個間隔，滿足第二式的整數會是每 $m_2$ 一個間隔，於是要同時滿足這兩個式子的整數間隔應為 $m_1$ 和 $m_2$ 的最小公倍數，在它們互質的前提之下即為兩數乘積，前兩式的通解即為 $x\equiv m_1\cdot t_0\cdot r + r_1$ (mod $m_1\cdot m_2$)。

例題：zerojudge c641。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


int N:=; // 式子的數量
int r[N], m[N]; // 餘數與除數

inline int nnm(int i, int n) { // nonnegative modulo
    return (i % n + n) % n;
}

for (int i=0; i<N; i++) cin >> r[i] >> m[i]; // 餘數與除數

// let x = r[0] (mod m[0]) and x = r[1] (mod m[1]),
// then m[0] * t + r[0] = r[1] (mod m[1])
//  ==> m[0] * t + m[1] * k = r[1] - r[0] (mod m[1]).
// Suppose m[0] * t0 + m[1] * k0 = 1, then
// x == m[0] * t0 * {r[1] - r[0] (mod m[1])} + r[0] (mod m[0]*m[1]).
for (int i=0; i+1<N; i++) {
    int a=m[i], b=m[i+1], x1=1, y1=0, x2=0, y2=1;
    do {
        int q = (a*x1 + b*y1) / (a*x2 + b*y2);
        int x3 = x1 - q*x2;
        int y3 = y1 - q*y2;
        x1 = x2; y1 = y2; x2 = x3; y2 = y3;
    } while (a*x2 + b*y2);
    x1 = (x1 + b) % b; // x1 is t0 mentioned above.
    r[i+1] = m[i] * x1 * nnm(r[i+1]-r[i], m[i+1]) + r[i];
    m[i+1] *= m[i];
    r[i+1] %= m[i+1];
}
cout << r[N-1] << '\n';