中国剩余定理

引入

「物不知数」问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即求满足以下条件的整数：除以 $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}, \dots, n_{k}$ 两两互质）：

{\begin{cases} x & \equiv a_{1} (\mod n_{1}) \\ x & \equiv a_{2} (\mod n_{2}) \\ ⋮ \\ x & \equiv a_{k} (\mod n_{k}) \end{cases}

上面的「物不知数」问题就是一元线性同余方程组的一个实例。

过程

计算所有模数的积 $n$ ；
对于第 $i$ 个方程：
1. 计算 $m_{i} = \frac{n}{n_{i}}$ ；
2. 计算 $m_{i}$ 在模 $n_{i}$ 意义下的逆元 $m_{i}^{- 1}$ ；
3. 计算 $c_{i} = m_{i} m_{i}^{- 1}$ （不要对 $n_{i}$ 取模）。
方程组在模 $n$ 意义下的唯一解为： $x = \sum_{i = 1}^{k} a_{i} c_{i} (\mod n)$ 。

实现

C++Python

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;
}

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, \dots, k$ 满足 $x \equiv a_{i} (\mod n_{i})$ 。

当 $i \neq j$ 时，有 $m_{j} \equiv 0 (\mod n_{i})$ ，故 $c_{j} \equiv m_{j} \equiv 0 (\mod n_{i})$ 。又有 $c_{i} \equiv m_{i} \cdot (m_{i}^{- 1} mod n_{i}) \equiv 1 (\mod n_{i})$ ，所以我们有：

\begin{aligned} x & \equiv \sum_{j = 1}^{k} a_{j} c_{j} & (\mod n_{i}) \\ \equiv a_{i} c_{i} & (\mod n_{i}) \\ \equiv a_{i} \cdot m_{i} \cdot (m_{i}^{- 1} mod n_{i}) & (\mod n_{i}) \\ \equiv a_{i} & (\mod n_{i}) \end{aligned}

即对于任意 $i = 1, 2, \dots, k$ ，上面算法得到的 $x$ 总是满足 $x \equiv a_{i} (\mod n_{i})$ ，即证明了解同余方程组的算法的正确性。

因为我们没有对输入的 $a_{i}$ 作特殊限制，所以任何一组输入 ${a_{i}}$ 都对应一个解 $x$ 。

另外，若 $x \neq y$ ，则总存在 $i$ 使得 $x$ 和 $y$ 在模 $n_{i}$ 下不同余。

故系数列表 ${a_{i}}$ 与解 $x$ 之间是一一映射关系，方程组总是有唯一解。

解释

下面演示 CRT 如何解「物不知数」问题。

$n = 3 \times 5 \times 7 = 105$ ；
三人同行七十希： $n_{1} = 3, m_{1} = n / n_{1} = 35, m_{1}^{- 1} \equiv 2 (\mod 3)$ ，故 $c_{1} = 35 \times 2 = 70$ ；
五树梅花廿一支： $n_{2} = 5, m_{2} = n / n_{2} = 21, m_{2}^{- 1} \equiv 1 (\mod 5)$ ，故 $c_{2} = 21 \times 1 = 21$ ；
七子团圆正半月： $n_{3} = 7, m_{3} = n / n_{3} = 15, m_{3}^{- 1} \equiv 1 (\mod 7)$ ，故 $c_{3} = 15 \times 1 = 15$ ；
所以方程组的唯一解为 $x \equiv 2 \times 70 + 3 \times 21 + 2 \times 15 \equiv 233 \equiv 23 (\mod 105)$ 。（除 百零五 便得知）

Garner 算法

CRT 的另一个用途是用一组比较小的质数表示一个大的整数。

例如，若 $a$ 满足如下线性方程组，且 $a < \prod_{i = 1}^{k} p_{i}$ （其中 $p_{i}$ 为质数）：

{\begin{cases} a & \equiv a_{1} (\mod p_{1}) \\ a & \equiv a_{2} (\mod p_{2}) \\ ⋮ \\ a & \equiv a_{k} (\mod p_{k}) \end{cases}

我们可以用以下形式的式子（称作 $a$ 的混合基数表示）表示 $a$ ：

a = x_{1} + x_{2} p_{1} + x_{3} p_{1} p_{2} + \dots + x_{k} p_{1} \dots p_{k - 1}

Garner 算法 将用来计算系数 $x_{1}, \dots, x_{k}$ 。

令 $r_{i j}$ 为 $p_{i}$ 在模 $p_{j}$ 意义下的逆：

p_{i} \cdot r_{i, j} \equiv 1 (\mod p_{j})

把 $a$ 代入我们得到的第一个方程：

a_{1} \equiv x_{1} (\mod p_{1})

代入第二个方程得出：

a_{2} \equiv x_{1} + x_{2} p_{1} (\mod p_{2})

方程两边减 $x_{1}$ ，除 $p_{1}$ 后得

\begin{aligned} a_{2} - x_{1} & \equiv x_{2} p_{1} & (\mod p_{2}) \\ (a_{2} - x_{1}) r_{1, 2} & \equiv x_{2} & (\mod p_{2}) \\ x_{2} & \equiv (a_{2} - x_{1}) r_{1, 2} & (\mod p_{2}) \end{aligned}

类似地，我们可以得到：

x_{k} = (\dots ((a_{k} - x_{1}) r_{1, k} - x_{2}) r_{2, k}) - \dots) r_{k - 1, k} mod p_{k}

实现

C++Python

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];
  }
}

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} Chinese Remainder Algorithm cra (v, m) : \\ Input : m = (m_{0}, m_{1}, \dots, m_{n - 1}), m_{i} \in Z^{+} \land gcd (m_{i}, m_{j}) = 1 for all i \neq j, \\ v = (v_{0}, \dots, v_{n - 1}) where v_{i} = x mod m_{i} . \\ Output : x mod \prod_{i = 0}^{n - 1} m_{i} . \\ 1 & for i from 1 to (n - 1) do \\ 2 & C_{i} \leftarrow {(\prod_{j = 0}^{i - 1} m_{j})}^{- 1} mod m_{i} \\ 3 & x \leftarrow v_{0} \\ 4 & for i from 1 to (n - 1) do \\ 5 & u \leftarrow (v_{i} - x) \cdot C_{i} mod m_{i} \\ 6 & x \leftarrow x + u \prod_{j = 0}^{i - 1} m_{j} \\ 7 & return (x) \end{array}

可以发现在第六行中的计算过程对应上述混合基数的表示。

应用

某些计数问题或数论问题出于加长代码、增加难度、或者是一些其他原因，给出的模数：不是质数！

但是对其质因数分解会发现它没有平方因子，也就是该模数是由一些不重复的质数相乘得到。

那么我们可以分别对这些模数进行计算，最后用 CRT 合并答案。

下面这道题就是一个不错的例子。

洛谷 P2480 [SDOI2010] 古代猪文

给出 $G, n$ （ $1 \leq G, n \leq 10^{9}$ ），求：

G^{\sum_{k ∣ n} (\binom{n}{k})} mod 999 911 659

首先，当 $G = 999 911 659$ 时，所求显然为 $0$ 。

否则，根据欧拉定理，可知所求为：

G^{\sum_{k ∣ n} (\binom{n}{k}) mod 999 911 658} mod 999 911 659

现在考虑如何计算：

\sum_{k ∣ n} (\binom{n}{k}) mod 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 ∣ n} (\binom{n}{k})$ 在模 $2$ ， $3$ ， $4679$ ， $35617$ 这几个质数下的结果，最后用中国剩余定理来合并答案。

也就是说，我们实际上要求下面一个线性方程组的解：

{\begin{cases} x \equiv a_{1} (\mod 2) \\ x \equiv a_{2} (\mod 3) \\ x \equiv a_{3} (\mod 4679) \\ x \equiv a_{4} (\mod 35617) \end{cases}

而计算一个组合数对较小的质数取模后的结果，可以利用卢卡斯定理。

扩展：模数不互质的情况

两个方程

设两个方程分别是 $x \equiv a_{1} (\mod m_{1})$ 、 $x \equiv a_{2} (\mod m_{2})$ ；

将它们转化为不定方程： $x = m_{1} p + a_{1} = m_{2} q + a_{2}$ ，其中 $p, q$ 是整数，则有 $m_{1} p - m_{2} q = a_{2} - a_{1}$ 。

由裴蜀定理，当 $a_{2} - a_{1}$ 不能被 $gcd (m_{1}, m_{2})$ 整除时，无解；

其他情况下，可以通过扩展欧几里得算法解出来一组可行解 $(p, q)$ ；

则原来的两方程组成的模方程组的解为 $x \equiv b (\mod M)$ ，其中 $b = m_{1} p + a_{1}$ ， $M = lcm (m_{1}, m_{2})$ 。

多个方程

用上面的方法两两合并即可。

习题

【模板】中国剩余定理（CRT）/曹冲养猪
【模板】扩展中国剩余定理
「NOI2018」屠龙勇士
「TJOI2009」猜数字

本页面部分内容译自博文 Китайская теорема об остатках 与其英文翻译版 Chinese Remainder Theorem。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。

本页面最近更新：2024/5/8 20:33:33，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：StudyingFather, Chrogeek, iamtwz, 383494, ChungZH, countercurrent-time, Early0v0, Enter-tainer, Great-designer, H-J-Granger, Haohu Shen, Henry-ZHR, hly1204, ImpleLee, Ir1d, kzoacn, little-cindy, MegaOwIer, Menci, NachtgeistW, namasikanam, ouuan, Phemon, renbaoshuo, shawlleyw, sshwy, stevebraveman, SukkaW, Tiphereth-A, Unnamed2964, Xeonacid, xyf007, Yanjun-Zhao
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用