Skip to content

中国剩余定理学习笔记

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

前置知识

中国剩余定理

中国剩余定理(Chinese Remainder Theorem,CRT)可求解如下形式的一元线性同余方程组(其中 n1,n2, ,nkn_1, n_2, \cdots, n_k 两两互质):

{xa1(modn1)xa2(modn2)xak(modnk)\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. 计算所有模数的积 nn
  2. 对于第 ii 个方程:
    1. 计算 mi=nnim_i = \frac{n}{n_i}
    2. 计算 mim_i 在模 nin_i 意义下的 逆元 mi1m_i^{-1}
    3. ii 个方程的解 ci=mi×mi1c_i = m_i \times m_i^{-1}(不要对 nin_i 取模)。
  3. 求出方程组的唯一解 x=i=1kaimici(modn)x = \sum_{i = 1}^k a_i m_i c_i \pmod n

代码实现

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

证明

因为 mi=nnim_i = \frac{n}{n_i} 是除 mim_i 之外所有模数的倍数,所以 ki,aimici0(modmk)\forall k \ne i, a_i m_i c_i \equiv 0 \pmod{m_k}。又因为 aimiciai(modmi)a_i m_i c_i \equiv a_i \pmod{m_i},所以代入 x=i=1naimicix = \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 日。