跳转至

中國剩餘定理

引入

「物不知數」問題：有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？

即求滿足以下條件的整數：除以 \(3\) 餘 \(2\)，除以 \(5\) 餘 \(3\)，除以 \(7\) 餘 \(2\)。

該問題最早見於《孫子算經》中，並有該問題的具體解法。宋朝數學家秦九韶於 1247 年《數書九章》卷一、二《大衍類》對「物不知數」問題做出了完整系統的解答。上面具體問題的解答口訣由明朝數學家程大位在《算法統宗》中給出：

三人同行七十希，五樹梅花廿一支，七子團圓正半月，除百零五便得知。

\(2\times 70+3\times 21+2\times 15=233=2\times 105+23\)，故答案為 \(23\)。

定義

中國剩餘定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元線性同餘方程組（其中 \(n_1, n_2, \cdots, n_k\) 兩兩互質）：

\[ \begin{cases} x &\equiv a_1 \pmod {n_1} \\ x &\equiv a_2 \pmod {n_2} \\ &\vdots \\ x &\equiv a_k \pmod {n_k} \\ \end{cases} \]

上面的「物不知數」問題就是一元線性同餘方程組的一個實例。

過程

  1. 計算所有模數的積 \(n\)；
  2. 對於第 \(i\) 個方程：
    1. 計算 \(m_i=\frac{n}{n_i}\)；
    2. 計算 \(m_i\) 在模 \(n_i\) 意義下的 逆元 \(m_i^{-1}\)；
    3. 計算 \(c_i=m_im_i^{-1}\)（不要對 \(n_i\) 取模）。
  3. 方程組在模 \(n\) 意義下的唯一解為：\(x=\sum_{i=1}^k a_ic_i \pmod n\)。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
LL CRT(int k, LL* a, LL* r) {
  LL n = 1, ans = 0;
  for (int i = 1; i <= k; i++) n = n * r[i];
  for (int i = 1; i <= k; i++) {
    LL m = n / r[i], b, y;
    exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
    ans = (ans + a[i] * m * b % n) % n;
  }
  return (ans % n + n) % n;
}

1
2
3
4
5
6
7
8
9
def CRT(k, a, r):
    n = 1; ans = 0
    for i in range(1, k + 1):
        n = n * r[i]
    for i in range(1, k + 1):
        m = n // r[i]; b = y = 0
        exgcd(m, r[i], b, y) # b * m mod r[i] = 1
        ans = (ans + a[i] * m * b % n) % n
    return (ans % n + n) % n

證明

我們需要證明上面算法計算所得的 \(x\) 對於任意 \(i=1,2,\cdots,k\) 滿足 \(x\equiv a_i \pmod {n_i}\)。

當 \(i\neq j\) 時，有 \(m_j \equiv 0 \pmod {n_i}\)，故 \(c_j \equiv m_j \equiv 0 \pmod {n_i}\)。又有 \(c_i \equiv m_i \cdot (m_i^{-1} \bmod {n_i}) \equiv 1 \pmod {n_i}\)，所以我們有：

\[ \begin{aligned} x&\equiv \sum_{j=1}^k a_jc_j &\pmod {n_i} \\ &\equiv a_ic_i &\pmod {n_i} \\ &\equiv a_i \cdot m_i \cdot (m^{-1}_i \bmod n_i) &\pmod {n_i} \\ &\equiv a_i &\pmod {n_i} \end{aligned} \]

即對於任意 \(i=1,2,\cdots,k\)，上面算法得到的 \(x\) 總是滿足 \(x\equiv a_i \pmod{n_i}\)，即證明了解同餘方程組的算法的正確性。

因為我們沒有對輸入的 \(a_i\) 作特殊限制，所以任何一組輸入 \(\{a_i\}\) 都對應一個解 \(x\)。

另外，若 \(x\neq y\)，則總存在 \(i\) 使得 \(x\) 和 \(y\) 在模 \(n_i\) 下不同餘。

故係數列表 \(\{a_i\}\) 與解 \(x\) 之間是一一映射關係，方程組總是有唯一解。

解釋

下面演示 CRT 如何解「物不知數」問題。

  1. \(n=3\times 5\times 7=105\)；
  2. 三人同行 七十 希：\(n_1=3, m_1=n/n_1=35, m_1^{-1}\equiv 2\pmod 3\)，故 \(c_1=35\times 2=70\)；
  3. 五樹梅花 廿一 支：\(n_2=5, m_2=n/n_2=21, m_2^{-1}\equiv 1\pmod 5\)，故 \(c_2=21\times 1=21\)；
  4. 七子團圓正 半月：\(n_3=7, m_3=n/n_3=15, m_3^{-1}\equiv 1\pmod 7\)，故 \(c_3=15\times 1=15\)；
  5. 所以方程組的唯一解為 \(x\equiv 2\times 70+3\times 21+2\times 15\equiv 233\equiv 23 \pmod {105}\)。（除 百零五 便得知）

Garner 算法

CRT 的另一個用途是用一組比較小的質數表示一個大的整數。

例如，若 \(a\) 滿足如下線性方程組，且 \(a < \prod_{i=1}^k p_i\)（其中 \(p_i\) 為質數）：

\[ \begin{cases} a &\equiv a_1 \pmod {p_1} \\ a &\equiv a_2 \pmod {p_2} \\ &\vdots \\ a &\equiv a_k \pmod {p_k} \\ \end{cases} \]

我們可以用以下形式的式子（稱作 \(a\) 的混合基數表示）表示 \(a\)：

\[ a = x_1 + x_2 p_1 + x_3 p_1 p_2 + \ldots + x_k p_1 \ldots p_{k-1} \]

Garner 算法 將用來計算係數 \(x_1, \ldots, x_k\)。

令 \(r_{ij}\) 為 \(p_i\) 在模 \(p_j\) 意義下的 逆：

\[ p_i \cdot r_{i,j} \equiv 1 \pmod{p_j} \]

把 \(a\) 代入我們得到的第一個方程：

\[ a_1 \equiv x_1 \pmod{p_1} \]

代入第二個方程得出：

\[ a_2 \equiv x_1 + x_2 p_1 \pmod{p_2} \]

方程兩邊減 \(x_1\)，除 \(p_1\) 後得

\[ \begin{aligned} a_2 - x_1 &\equiv x_2 p_1 &\pmod{p_2} \\ (a_2 - x_1) r_{1,2} &\equiv x_2 &\pmod{p_2} \\ x_2 &\equiv (a_2 - x_1) r_{1,2} &\pmod{p_2} \end{aligned} \]

類似地，我們可以得到：

\[ x_k=(\dots((a_k-x_1)r_{1,k}-x_2)r_{2,k})-\dots)r_{k-1,k} \bmod p_k \]
實現 
1
2
3
4
5
6
7
8
for (int i = 0; i < k; ++i) {
  x[i] = a[i];
  for (int j = 0; j < i; ++j) {
    x[i] = r[j][i] * (x[i] - x[j]);
    x[i] = x[i] % p[i];
    if (x[i] < 0) x[i] += p[i];
  }
}

1
2
3
4
5
6
7
for i in range(0, k):
    x[i] = a[i]
    for j in range(0, i):
        x[i] = r[j][i] * (x[i] - x[j])
        x[i] = x[i] % p[i]
        if (x[i] < 0):
            x[i] = x[i] + p[i]

該算法的時間複雜度為 \(O(k^2)\)。實際上 Garner 算法並不要求模數為質數，只要求模數兩兩互質，我們有如下偽代碼：

\[ \begin{array}{ll} &\textbf{Chinese Remainder Algorithm }\operatorname{cra}(\mathbf{v}, \mathbf{m})\text{:} \\ &\textbf{Input}\text{: }\mathbf{m}=(m_0,m_1,\dots ,m_{n-1})\text{, }m_i\in\mathbb{Z}^+\land\gcd(m_i,m_j)=1\text{ for all } i\neq j\text{,} \\ &\qquad \mathbf{v}=(v_0,\dots ,v_{n-1}) \text{ where }v_i=x\bmod m_i\text{.} \\ &\textbf{Output}\text{: }x\bmod{\prod_{i=0}^{n-1} m_i}\text{.} \\ 1&\qquad \textbf{for }i\text{ from }1\text{ to }(n-1)\textbf{ do} \\ 2&\qquad \qquad C_i\gets \left(\prod_{j=0}^{i-1}m_j\right)^{-1}\bmod{m_i} \\ 3&\qquad x\gets v_0 \\ 4&\qquad \textbf{for }i\text{ from }1\text{ to }(n-1)\textbf{ do} \\ 5&\qquad \qquad u\gets (v_i-x)\cdot C_i\bmod{m_i} \\ 6&\qquad \qquad x\gets x+u\prod_{j=0}^{i-1}m_j \\ 7&\qquad \textbf{return }(x) \end{array} \]

可以發現在第六行中的計算過程對應上述混合基數的表示。

應用

某些計數問題或數論問題出於加長代碼、增加難度、或者是一些其他原因，給出的模數：不是質數！

但是對其質因數分解會發現它沒有平方因子，也就是該模數是由一些不重複的質數相乘得到。

那麼我們可以分別對這些模數進行計算，最後用 CRT 合併答案。

下面這道題就是一個不錯的例子。

洛谷 P2480 [SDOI2010] 古代豬文

給出 \(G,n\)（\(1 \leq G,n \leq 10^9\)），求：

\[ G^{\sum_{k\mid n}\binom{n}{k}} \bmod 999~911~659 \]

首先，當 \(G=999~911~659\) 時，所求顯然為 \(0\)。

否則，根據 歐拉定理，可知所求為：

\[ G^{\sum_{k\mid n}\binom{n}{k} \bmod 999~911~658} \bmod 999~911~659 \]

現在考慮如何計算：

\[ \sum_{k\mid n}\binom{n}{k} \bmod 999~911~658 \]

因為 \(999~911~658\) 不是質數，無法保證 \(\forall x \in [1,999~911~657]\)，\(x\) 都有逆元存在，上面這個式子我們無法直接計算。

注意到 \(999~911~658=2 \times 3 \times 4679 \times 35617\)，其中每個質因子的最高次數均為一，我們可以考慮分別求出 \(\sum_{k\mid n}\binom{n}{k}\) 在模 \(2\)，\(3\)，\(4679\)，\(35617\) 這幾個質數下的結果，最後用中國剩餘定理來合併答案。

也就是説，我們實際上要求下面一個線性方程組的解：

\[ \begin{cases} x \equiv a_1 \pmod 2\\ x \equiv a_2 \pmod 3\\ x \equiv a_3 \pmod {4679}\\ x \equiv a_4 \pmod {35617} \end{cases} \]

而計算一個組合數對較小的質數取模後的結果，可以利用 盧卡斯定理。

擴展：模數不互質的情況

兩個方程

設兩個方程分別是 \(x\equiv a_1 \pmod {m_1}\)、\(x\equiv a_2 \pmod {m_2}\)；

將它們轉化為不定方程：\(x=m_1p+a_1=m_2q+a_2\)，其中 \(p, q\) 是整數，則有 \(m_1p-m_2q=a_2-a_1\)。

由 裴蜀定理，當 \(a_2-a_1\) 不能被 \(\gcd(m_1,m_2)\) 整除時，無解；

其他情況下，可以通過 擴展歐幾里得算法 解出來一組可行解 \((p, q)\)；

則原來的兩方程組成的模方程組的解為 \(x\equiv b\pmod M\)，其中 \(b=m_1p+a_1\)，\(M=\text{lcm}(m_1, m_2)\)。

多個方程

用上面的方法兩兩合併即可。

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用