定义

中国剩余定理（Chinese Remainder Theorem，CRT），可用于求解如下形式的一元线性同余方程组（其中 $a_1,a_2,…,a_3$ 两两互质 ）：

$$\begin{cases} x \equiv a_1\ ({\rm mod}\ n_1) \ x\equiv a_2\ ({\rm mod}\ n_2) \ … \ x \equiv a_k\ ({\rm mod}\ n_k)\end{cases}$$

（我习惯看成 $a \equiv c\ ({\rm mod}\ b)$ ，即 $a\%b=c$ ）

解法

• 先求出模数的积 $N$ ，设 $N=\prod_{i=1}^k n_i$

• 对于第 $i$ 个方程：

  • 先求除了 $n_i$ 外的所有模数之积，设 $N_i=\frac{N}{n_i}$
  • 求 $N_i$ 在模 $n_i$ 意义下的逆元 $N_i^{-1}$ ，即 $N_i\times N_i^{-1} \equiv 1\ ({\rm mod}\ n_i)$

• 最小正整数解 $x=\sum_{i=1}^k a_i\times N_i\times N_i^{-1}$

证明

对于第 $i$ 个方程：

• 当 $i\not = j$ 时，有 $a_j\times N_j\times N_j^{-1} \equiv 0\ ({\rm mod}\ n_i)$ ，因为 $N_j$ 中必然有 $n_i$ 。
• 当 $i=j$ 时，有$a_i\times N_i\times N_i^{-1} \equiv a_i\ ({\rm mod}\ n_i)$ 。

因此，$\sum_{i=1}^k a_i\times N_i\times N_i^{-1}\equiv a_i\ ({\rm mod}\ n_i)$ 。

实现

ll CRT() {
    ll s = 1, ans = 0;
    for (int i = 1; i <= n; i++)s *= b[i];
    for (int i = 1; i <= n; i++) {
        ll x, y, r = s / b[i];
        exgcd(r, b[i], x, y);   //求逆元
        (ans += c[i] * r * x) %= s;
    }
    return (ans % s + s) % s;
}

扩展中国剩余定理

定义

$$\begin{cases} x \equiv a_1\ ({\rm mod}\ n_1) \ x\equiv a_2\ ({\rm mod}\ n_2) \ … \ x \equiv a_k\ ({\rm mod}\ n_k)\end{cases}$$

仍然是这个方程组，但此时模数不互质了。

解法和证明

由于模数不互质，$N_i$ 与 $n_i$ 也不互质，则不存在 $N_i$ 的逆元。此时再用原算法算就不对了。

于是可以考虑换一种方法，基本想法就是考虑将两个同余方程合并为一个，依次求解。

$$\begin{cases} x \equiv a_1\ ({\rm mod}\ n_1) \ x\equiv a_2\ ({\rm mod}\ n_2) \ \end{cases}$$

对于这两个方程，我们可以把它写成：

$$ x=k_1 n_1+a_1=k_2 n_2+a_2 $$

移项一下，有：

$$ k_1n_1-k_2n_2=a_2-a_1 $$

可以发现，式子中只有 $k_1,k_2$ 两个未知数，可以用扩展欧几里得算法求出 $k_1,k_2$ 一组解：

设 $g=gcd(n_1,n_2)$ ，$k_1′,k_2’$ 为 exgcd 求出的值。

$$\begin{cases} k_1=\frac{k_1′(a_2-a_1)}{g} \ k_2=\frac{k_2′(a_2-a_1)}{g}\ \end{cases}$$

代回原式即可得到方程组的一组特解：

$$x_0=\frac{k_1′(a_2-a_1)}{g}n_1+a_1$$

而方程组的通解即为：

$$x=x_0\ \pm\ K\cdot lcm(n_1\ ,\ n_2)$$

这个式子又等价于这样一个新的方程：

$$x\equiv x_0\ ({\rm mod}\ lcm(n_1,n_2)) $$

这样我们就成功把两个方程合并为一个了。

主要思路就是这样，至于一些更细节的证明，这边建议看模板题题解区，大佬们讲的更好orz。

实现

实现起来有点不太好写，这里的写法借鉴了题解区的大佬的写法。

ll mul(ll n, ll k, ll mod) {    //龟速乘
    ll ans = 0;
    while (k) {
        if (k & 1) ans = (ans + n) % mod;
        k >>= 1;
        n = (n + n) % mod;
    }
    return ans;
}

ll exCRT() {
    ll ans = c[1];
    ll M = b[1];
    for (int i = 2; i <= n; i++) {
        ll x, y, C = ((c[i] - ans) % b[i] + b[i]) % b[i];
        ll g = exgcd(M, b[i], x, y);//求x*b[i-1]-y*b[i]=gcd(b[i-1],b[i])的解
        x = mul(x, C / g, b[i]);    //龟速乘，求原方程x*b[i-1]-y*b[i]=c[i]-c[i-1]的解
        ans += M * x;
        M *= b[i] / g;
        ans = (ans + M) % M;    //更新通解
    }
    return ans;
}