中国剩余定理学习笔记

#前置知识

• 扩展欧几里得算法
• 线性同余方程

#中国剩余定理

中国剩余定理（Chinese Remainder Theorem，CRT）可求解如下形式的一元线性同余方程组（其中 $n_1, n_2, \cdots, n_k$ 两两互质）：

$$\begin{cases} \begin{array}{cl} x \equiv a_1 & \pmod{n_1} \\ x \equiv a_2 & \pmod{n_2} \\ \ldots & \\ x \equiv a_k & \pmod{n_k} \\ \end{array} \end{cases}$$

#算法流程

1. 计算所有模数的积 $n$；
2. 对于第 $i$ 个方程：
   1. 计算 $m_i = \frac{n}{n_i}$；
   2. 计算 $m_i$ 在模 $n_i$ 意义下的 逆元 $m_i^{-1}$；
   3. 第 $i$ 个方程的解 $c_i = m_i \times m_i^{-1}$（不要对 $n_i$ 取模）。
3. 求出方程组的唯一解 $x = \sum_{i = 1}^k a_i m_i c_i \pmod n$。

#代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

long long CRT() {
    long long mod = 1, ans = 0;

    for (int i = 1; i <= n; i++) {
        mod *= n[i];
    }

    for (int i = 1; i <= n; i++) {
        long long m = mod / n[i], x, y;
        exgcd(m, n[i], x, y);
        ans = (ans + a[i] * m * x % mod) % mod;
    }

    return (ans % mod + mod) % mod;
}

#证明

因为 $m_i = \frac{n}{n_i}$ 是除 $m_i$ 之外所有模数的倍数，所以 $\forall k \ne i, a_i m_i c_i \equiv 0 \pmod{m_k}$。又因为 $a_i m_i c_i \equiv a_i \pmod{m_i}$，所以代入 $x = \sum^{n}_{i = 1} a_i m_i c_i$，原方程组成立。

证毕。

#参考资料

1. 第 154 ~ 155 页，0x33 同余，《算法竞赛进阶指南》（ISBN 978-7-83009-313-6，河南电子音像出版社），李煜东，2019 年 5 月第 5 次修订版。
2. 1.5 中国剩余定理，《信息学奥赛之数学一本通》（ISBN 978-7-5641-6576-5，东南大学出版社），林厚从，2019 年 11 月第 9 次修订版。
3. 中国剩余定理，OI Wiki，2022 年 3 月 27 日。