中国剩余定理学习笔记

引入

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

即求满足以下条件的整数：除以 $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)$ 。

实现

cpp

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

证明

我们需要证明上面算法计算所得的 $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}

该算法的时间复杂度为 $O (k^{2})$ 。实际上 Garner 算法并不要求模数为质数，只要求模数两两互质

应用

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

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

那么我们可以分别对这些模数进行计算，最后用 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})$ 。

多个方程

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

中国剩余定理 学习笔记 ​

引入 ​

定义 ​

过程 ​

实现 ​

证明 ​

解释 ​

Garner 算法 ​

应用 ​

洛谷 P2480 [SDOI2010] 古代猪文 ​

扩展：模数不互质的情况 ​

两个方程 ​

多个方程 ​

习题 ​

中国剩余定理学习笔记

引入

定义

过程

实现

证明

解释

Garner 算法

应用

洛谷 P2480 [SDOI2010] 古代猪文

扩展：模数不互质的情况

两个方程

多个方程

习题