# 算法讲义：中国剩余定理 (Chinese Remainder Theorem)

## 1. 经典中国剩余定理 (孙子定理)

### 1.1 问题引入
《孙子算经》中著名的“物不知其数”问题：
> “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”

转换成现代数学语言，即求解同余方程组：
$$
\begin{cases} 
x \equiv a\_1 \pmod{m\_1} \
x \equiv a\_2 \pmod{m\_2} \
\dots \
x \equiv a\_n \pmod{m\_n}
\end{cases}
$$
在**经典 CRT** 中，要求 $m\_1, m\_2, \dots, m\_n$ **两两互质**。

### 1.2 构造法求解步骤
1.  计算所有模数的乘积 $M = \prod\_{i=1}^n m\_i$。
2.  对于每个方程 $i$：
    - 计算 $M\_i = M / m\_i$（即除 $m\_i$ 外其余模数的乘积）。
    - 计算 $M\_i$ 模 $m\_i$ 的逆元 $t\_i$，即满足 $M\_i t\_i \equiv 1 \pmod{m\_i}$。
3.  方程组的一个特解为：$x\_0 = \sum\_{i=1}^n a\_i M\_i t\_i$。
4.  通解为：$x = x\_0 + kM$。最小正整数解为 $x\_0 \bmod M$。

### 1.3 代码实现 (C++)
```cpp
typedef long long ll;

// 扩展欧几里得算法求逆元
void exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1, y = 0; return; }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

ll crt(int n, ll a[], ll m[]) {
    ll M = 1, ret = 0;
    for (int i = 0; i < n; i++) M *= m[i];
    for (int i = 0; i < n; i++) {
        ll Mi = M / m[i];
        ll x, y;
        exgcd(Mi, m[i], x, y); // 求 Mi 在模 mi 下的逆元 x
        x = (x % m[i] + m[i]) % m[i]; // 保证 x 为正
        ret = (ret + a[i] * Mi % M * x % M) % M;
    }
    return (ret + M) % M;
}
```

**复杂度**：$O(n \log m)$，其中 $m$ 是模数的大小。

---

## 2. 扩展中国剩余定理 (EXCRT)

### 2.1 为什么要扩展？
当模数 $m\_i, m\_j$ **不互质**时，经典 CRT 失效（因为 $M\_i$ 模 $m\_i$ 的逆元可能不存在）。此时需要使用**两两合并**的思想。

### 2.2 方程合并推导
假设已有两个方程：
1. $x = k\_1 m\_1 + a\_1$
2. $x = k\_2 m\_2 + a\_2$

联立得：
$$k\_1 m\_1 + a\_1 = k\_2 m\_2 + a\_2 \implies k\_1 m\_1 - k\_2 m\_2 = a\_2 - a\_1$$

这是一个关于 $k\_1, k\_2$ 的**二元一次不定方程**。根据裴蜀定理：
- **无解判定**：若 $(a\_2 - a\_1) \bmod \gcd(m\_1, m\_2) \neq 0$，则方程组无解。
- **求解 $k\_1$**：利用 `exgcd` 求出 $k\_1 m\_1 + k\_2 (-m\_2) = \gcd(m\_1, m\_2)$ 的一个特解 $k\_{1}'$，然后放大 $\frac{a\_2-a\_1}{\gcd(m\_1, m\_2)}$ 倍。

得到 $k\_1$ 后，代入 $x = k\_1 m\_1 + a\_1$，可得新的通解形式：
$$x \equiv X\_{new} \pmod{\text{lcm}(m\_1, m\_2)}$$
其中 $X\_{new} = k\_1 m\_1 + a\_1$。

### 2.3 算法步骤
1. 初始化第一个方程：$M = m\_1, Ans = a\_1$。
2. 逐个合并后续方程 $(a\_i, m\_i)$：
   - 求解 $k \cdot M \equiv a\_i - Ans \pmod{m\_i}$。
   - 使用 `exgcd` 求出 $k$。
   - 更新 $Ans = Ans + k \cdot M$。
   - 更新 $M = \text{lcm}(M, m\_i)$。
3. 循环结束后的 $Ans \bmod M$ 即为答案。

### 2.4 代码实现 (C++)
```cpp
ll excrt(int n, ll a[], ll m[]) {
    ll m1 = m[0], a1 = a[0];
    for (int i = 1; i < n; i++) {
        ll m2 = m[i], a2 = a[i];
        ll x, y;
        ll g = __gcd(m1, m2);
        if ((a2 - a1) % g != 0) return -1; // 无解

exgcd(m1 / g, m2 / g, x, y); // 求解关键步骤
        
        // 计算当前 k1 的特解，注意防止溢出
        ll mod = m2 / g;
        x = (__int128)x * ((a2 - a1) / g) % mod;
        if (x < 0) x += mod;

// 合并方程
        a1 = a1 + x * m1;
        m1 = m1 / g * m2; // 新的模数是 lcm(m1, m2)
        a1 = (a1 % m1 + m1) % m1;
    }
    return a1;
}
```

---

## 3. CRT 与 EXCRT 总结对比

### 应用场景
1.  **大数取模**：当运算结果超过 `long long` 但模数是几个小质数的乘积。
2.  **Lucas 定理扩展**：当卢卡斯定理中的模数 $p$ 不是质数时，需分解质因数后用 CRT 合并。
3.  **密码学**：RSA 算法中的加速运算。

算法讲义：中国剩余定理 (Chinese Remainder Theorem)

1. 经典中国剩余定理 (孙子定理)

1.1 问题引入

《孙子算经》中著名的“物不知其数”问题：

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”

转换成现代数学语言，即求解同余方程组： $$ \begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \ \dots \ x \equiv a_n \pmod{m_n} \end{cases} $$ 在经典 CRT 中，要求 $m_1, m_2, \dots, m_n$ 两两互质。

1.2 构造法求解步骤

计算所有模数的乘积 $M = \prod_{i=1}^n m_i$。
对于每个方程 $i$：
- 计算 $M_i = M / m_i$（即除 $m_i$ 外其余模数的乘积）。
- 计算 $M_i$ 模 $m_i$ 的逆元 $t_i$，即满足 $M_i t_i \equiv 1 \pmod{m_i}$。
方程组的一个特解为：$x_0 = \sum_{i=1}^n a_i M_i t_i$。
通解为：$x = x_0 + kM$。最小正整数解为 $x_0 \bmod M$。

1.3 代码实现 (C++)

typedef long long ll;

// 扩展欧几里得算法求逆元
void exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1, y = 0; return; }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

ll crt(int n, ll a[], ll m[]) {
    ll M = 1, ret = 0;
    for (int i = 0; i < n; i++) M *= m[i];
    for (int i = 0; i < n; i++) {
        ll Mi = M / m[i];
        ll x, y;
        exgcd(Mi, m[i], x, y); // 求 Mi 在模 mi 下的逆元 x
        x = (x % m[i] + m[i]) % m[i]; // 保证 x 为正
        ret = (ret + a[i] * Mi % M * x % M) % M;
    }
    return (ret + M) % M;
}

复杂度：$O(n \log m)$，其中 $m$ 是模数的大小。

2. 扩展中国剩余定理 (EXCRT)

2.1 为什么要扩展？

当模数 $m_i, m_j$ 不互质时，经典 CRT 失效（因为 $M_i$ 模 $m_i$ 的逆元可能不存在）。此时需要使用两两合并的思想。

2.2 方程合并推导

假设已有两个方程： 1. $x = k_1 m_1 + a_1$ 2. $x = k_2 m_2 + a_2$

联立得： $$k_1 m_1 + a_1 = k_2 m_2 + a_2 \implies k_1 m_1 - k_2 m_2 = a_2 - a_1$$

这是一个关于 $k_1, k_2$ 的二元一次不定方程。根据裴蜀定理： - 无解判定：若 $(a_2 - a_1) \bmod \gcd(m_1, m_2) \neq 0$，则方程组无解。 - 求解 $k_1$：利用 exgcd 求出 $k_1 m_1 + k_2 (-m_2) = \gcd(m_1, m_2)$ 的一个特解 $k_{1}'$，然后放大 $\frac{a_2-a_1}{\gcd(m_1, m_2)}$ 倍。

得到 $k_1$ 后，代入 $x = k_1 m_1 + a_1$，可得新的通解形式： $$x \equiv X_{new} \pmod{\text{lcm}(m_1, m_2)}$$ 其中 $X_{new} = k_1 m_1 + a_1$。

2.3 算法步骤

初始化第一个方程：$M = m_1, Ans = a_1$。
逐个合并后续方程 $(a_i, m_i)$：
求解 $k \cdot M \equiv a_i - Ans \pmod{m_i}$。
使用 exgcd 求出 $k$。
更新 $Ans = Ans + k \cdot M$。
更新 $M = \text{lcm}(M, m_i)$。
循环结束后的 $Ans \bmod M$ 即为答案。

2.4 代码实现 (C++)

ll excrt(int n, ll a[], ll m[]) {
    ll m1 = m[0], a1 = a[0];
    for (int i = 1; i < n; i++) {
        ll m2 = m[i], a2 = a[i];
        ll x, y;
        ll g = __gcd(m1, m2);
        if ((a2 - a1) % g != 0) return -1; // 无解

        exgcd(m1 / g, m2 / g, x, y); // 求解关键步骤

        // 计算当前 k1 的特解，注意防止溢出
        ll mod = m2 / g;
        x = (__int128)x * ((a2 - a1) / g) % mod;
        if (x < 0) x += mod;

        // 合并方程
        a1 = a1 + x * m1;
        m1 = m1 / g * m2; // 新的模数是 lcm(m1, m2)
        a1 = (a1 % m1 + m1) % m1;
    }
    return a1;
}

3. CRT 与 EXCRT 总结对比

特性	经典 CRT	扩展 EXCRT
模数要求	必须两两互质	无限制
核心思想	构造法	方程两两合并
工具	逆元 (Inverse)	扩欧 (exgcd)
适用场景	模数较小且为质数乘积时	模数任意，通用性更强

应用场景

大数取模：当运算结果超过 long long 但模数是几个小质数的乘积。
Lucas 定理扩展：当卢卡斯定理中的模数 $p$ 不是质数时，需分解质因数后用 CRT 合并。
密码学：RSA 算法中的加速运算。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com