# 讲义：中国剩余定理（CRT）与扩展中国剩余定理（EXCRT）全解

---

## 引言

同余方程组在数论中占有核心地位。中国剩余定理（Chinese Remainder Theorem，简称 **CRT**）最早见于我国古代数学著作《孙子算经》中的“物不知数”问题。

本文将系统讲解如何求解一元线性同余方程组：
$$
\begin{cases}
x \equiv a\_1 \pmod{m\_1} \\\
x \equiv a\_2 \pmod{m\_2} \\\
\quad \vdots \\\
x \equiv a\_n \pmod{m\_n}
\end{cases}
$$

我们将分为两部分：第一部分讲解**模数两两互质**的经典中国剩余定理；第二部分讲解**模数不一定互质**的扩展中国剩余定理（EXCRT）。

---

## 第一部分：模数两两互质的中国剩余定理 (CRT)

### 1. 适用条件与原理
若模数 $m\_1, m\_2, \dots, m\_n$ **两两互质**，则方程组在模 $M = \prod\_{i=1}^{n} m\_i$ 的范围内有唯一解。

其核心构造思想如下：
1. 计算所有模数的乘积 $M = m\_1 m\_2 \dots m\_n$。
2. 对于第 $i$ 个方程，计算：
   $$M\_i = \frac{M}{m\_i}$$
3. 计算 $M\_i$ 在模 $m\_i$ 意义下的乘法逆元 $t\_i$，即满足：
   $$M\_i \cdot t\_i \equiv 1 \pmod{m\_i}$$
   （通常用扩展欧几里得算法 `exgcd` 求出）。
4. 方程组在模 $M$ 下的唯一正整数解 $x$ 为：
   $$x = \left( \sum\_{i=1}^{n} a\_i \cdot M\_i \cdot t\_i \right) \bmod M$$

### 2. 例题与解析
> **题目**：求一个最小的正整数 $x$，使得它除以 $m\_1, m\_2, \dots, m\_n$ 的余数分别是 $a\_1, a\_2, \dots, a\_n$。输入保证 $m\_i$ 两两互质。

#### C++11 代码实现
```cpp
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

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

// 中国剩余定理模板函数
ll chineseRemainder(int n, const vector<ll>& a, const vector<ll>& m) {
    ll M = 1;
    for (int i = 0; i < n; ++i) {
        M *= m[i];
    }

ll x_ans = 0;
    for (int i = 0; i < n; ++i) {
        ll Mi = M / m[i];
        ll ti, y;
        // 求 Mi 在模 mi 下的逆元 ti -> Mi * ti ≡ 1 (mod mi)
        exgcd(Mi, m[i], ti, y);
        ti = (ti % m[i] + m[i]) % m[i]; // 防止负数逆元
        
        // 累加各项 (注意防止溢出，视数据大小可使用 __int128)
        x_ans = (x_ans + (__int128)a[i] * Mi % M * ti) % M;
    }

return (x_ans % M + M) % M;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

int n;
    if (!(cin >> n)) return 0;

vector<ll> a(n), m(n);
    for (int i = 0; i < n; ++i) {
        cin >> m[i] >> a[i];
    }

ll ans = chineseRemainder(n, a, m);
    cout << ans << "\n";

return 0;
}
```

---

## 第二部分：模数不一定互质的扩展中国剩余定理 (EXCRT)

### 1. 原理与推导过程（两两合并法）

当模数 $m\_1, m\_2, \dots, m\_n$ **不保证两两互质**时，CRT 的乘法逆元法失效。此时采用**两两合并**的思想。

假设我们已经求出了前 $i-1$ 个方程的一个特解 $x$，其等效模数为 $M$。也就是说，前 $i-1$ 个方程的所有解可以表示为：
$$X = x + t \cdot M \quad (t \text{ 为整数})$$

现在加入第 $i$ 个方程：
$$X \equiv a\_i \pmod{m\_i}$$

代入后得到：
$$x + t \cdot M \equiv a\_i \pmod{m\_i} \implies M \cdot t \equiv a\_i - x \pmod{m\_i}$$

转化为二元一次不定方程（丢番图方程）：
$$M \cdot t + m\_i \cdot y = a\_i - x$$
令 $A = M, B = m\_i, C = a\_i - x$，利用 `exgcd(A, B, t, y)` 求解：
1. **无解判定**：若 $C$ 不能被 $\gcd(A, B)$ 整除，说明无解。
2. **求特解 $t$**：先通过扩展欧几里得求出基础解，再化为最小整数解 $t$。
3. **更新特解 $x$**：
   $$x\_{\text{new}} = x + t \cdot M\_{\text{old}}$$
4. **求新模数 $M\_{\text{new}}$**：
   新模数必须既是原模数 $M\_{\text{old}}$ 的倍数，又是当前模数 $m\_i$ 的倍数，因此新模数是它们的**最小公倍数（LCM）**：
   $$M\_{\text{new}} = \text{lcm}(M\_{\text{old}}, m\_i) = \frac{M\_{\text{old}}}{\gcd(M\_{\text{old}}, m\_i)} \cdot m\_i$$

---

### 2. 例题与解析
> **题目**：给定 $n$ 组非负整数 $a\_i, m\_i$，求解下列同余方程组的最小非负整数解（模数不保证互质）：
> $$
\begin{cases}
x \equiv a\_1 \pmod{m\_1} \\\
x \equiv a\_2 \pmod{m\_2} \\\
\quad \vdots \\\
x \equiv a\_n \pmod{m\_n}
\end{cases}
$$

#### C++11 代码实现
```cpp
#include <iostream>
#include <vector>

using namespace std;

typedef __int128_t int128; // 使用 128 位整型防止乘法溢出
typedef long long ll;

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

// 扩展中国剩余定理 (EXCRT)
ll exCRT(int n, const vector<ll>& a, const vector<ll>& m) {
    ll x = a[0]; 
    ll M = m[0];

for (int i = 1; i < n; ++i) {
        // 合并第 i 个方程: M * t ≡ (a[i] - x) (mod m[i])
        ll A = M, B = m[i];
        ll C = (a[i] - x % B + B) % B; 
        ll t, y;
        ll gcd_val = exgcd(A, B, t, y);

// 无解判定
        if (C % gcd_val != 0) {
            return -1;
        }

// 计算最小正整数解 t
        ll mod = B / gcd_val;
        t = (ll)((int128)t * (C / gcd_val) % mod);
        t = (t % mod + mod) % mod;

// 更新总解 x 和总模数 M (M 即为 lcm)
        x = x + t * M;
        M = M / gcd_val * B; 
        x = (x % M + M) % M;
    }

return (x % M + M) % M;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

int n;
    if (!(cin >> n)) return 0;

vector<ll> a(n), m(n);
    for (int i = 0; i < n; ++i) {
        cin >> m[i] >> a[i];
    }

ll ans = exCRT(n, a, m);
    cout << (ll)ans << "\n";

return 0;
}
```

讲义：中国剩余定理（CRT）与扩展中国剩余定理（EXCRT）全解

引言

同余方程组在数论中占有核心地位。中国剩余定理（Chinese Remainder Theorem，简称 CRT）最早见于我国古代数学著作《孙子算经》中的“物不知数”问题。

本文将系统讲解如何求解一元线性同余方程组： $$ \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \quad \vdots \\ x \equiv a_n \pmod{m_n} \end{cases} $$

我们将分为两部分：第一部分讲解模数两两互质的经典中国剩余定理；第二部分讲解模数不一定互质的扩展中国剩余定理（EXCRT）。

第一部分：模数两两互质的中国剩余定理 (CRT)

1. 适用条件与原理

若模数 $m_1, m_2, \dots, m_n$ 两两互质，则方程组在模 $M = \prod_{i=1}^{n} m_i$ 的范围内有唯一解。

其核心构造思想如下： 1. 计算所有模数的乘积 $M = m_1 m_2 \dots m_n$。 2. 对于第 $i$ 个方程，计算： $$M_i = \frac{M}{m_i}$$ 3. 计算 $M_i$ 在模 $m_i$ 意义下的乘法逆元 $t_i$，即满足： $$M_i \cdot t_i \equiv 1 \pmod{m_i}$$ （通常用扩展欧几里得算法 exgcd 求出）。 4. 方程组在模 $M$ 下的唯一正整数解 $x$ 为： $$x = \left( \sum_{i=1}^{n} a_i \cdot M_i \cdot t_i \right) \bmod M$$

2. 例题与解析

题目：求一个最小的正整数 $x$，使得它除以 $m_1, m_2, \dots, m_n$ 的余数分别是 $a_1, a_2, \dots, a_n$。输入保证 $m_i$ 两两互质。

C++11 代码实现

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

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

// 中国剩余定理模板函数
ll chineseRemainder(int n, const vector<ll>& a, const vector<ll>& m) {
    ll M = 1;
    for (int i = 0; i < n; ++i) {
        M *= m[i];
    }

    ll x_ans = 0;
    for (int i = 0; i < n; ++i) {
        ll Mi = M / m[i];
        ll ti, y;
        // 求 Mi 在模 mi 下的逆元 ti -> Mi * ti ≡ 1 (mod mi)
        exgcd(Mi, m[i], ti, y);
        ti = (ti % m[i] + m[i]) % m[i]; // 防止负数逆元

        // 累加各项 (注意防止溢出，视数据大小可使用 __int128)
        x_ans = (x_ans + (__int128)a[i] * Mi % M * ti) % M;
    }

    return (x_ans % M + M) % M;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<ll> a(n), m(n);
    for (int i = 0; i < n; ++i) {
        cin >> m[i] >> a[i];
    }

    ll ans = chineseRemainder(n, a, m);
    cout << ans << "\n";

    return 0;
}

第二部分：模数不一定互质的扩展中国剩余定理 (EXCRT)

1. 原理与推导过程（两两合并法）

当模数 $m_1, m_2, \dots, m_n$ 不保证两两互质时，CRT 的乘法逆元法失效。此时采用两两合并的思想。

现在加入第 $i$ 个方程： $$X \equiv a_i \pmod{m_i}$$

代入后得到： $$x + t \cdot M \equiv a_i \pmod{m_i} \implies M \cdot t \equiv a_i - x \pmod{m_i}$$

转化为二元一次不定方程（丢番图方程）： $$M \cdot t + m_i \cdot y = a_i - x$$ 令 $A = M, B = m_i, C = a_i - x$，利用 exgcd(A, B, t, y) 求解： 1. 无解判定：若 $C$ 不能被 $\gcd(A, B)$ 整除，说明无解。 2. 求特解 $t$：先通过扩展欧几里得求出基础解，再化为最小整数解 $t$。 3. 更新特解 $x$： $$x_{\text{new}} = x + t \cdot M_{\text{old}}$$ 4. 求新模数 $M_{\text{new}}$：新模数必须既是原模数 $M_{\text{old}}$ 的倍数，又是当前模数 $m_i$ 的倍数，因此新模数是它们的最小公倍数（LCM）： $$M_{\text{new}} = \text{lcm}(M_{\text{old}}, m_i) = \frac{M_{\text{old}}}{\gcd(M_{\text{old}}, m_i)} \cdot m_i$$

2. 例题与解析

题目：给定 $n$ 组非负整数 $a_i, m_i$，求解下列同余方程组的最小非负整数解（模数不保证互质）： $$ \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \quad \vdots \\ x \equiv a_n \pmod{m_n} \end{cases} $$

C++11 代码实现

#include <iostream>
#include <vector>

using namespace std;

typedef __int128_t int128; // 使用 128 位整型防止乘法溢出
typedef long long ll;

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

// 扩展中国剩余定理 (EXCRT)
ll exCRT(int n, const vector<ll>& a, const vector<ll>& m) {
    ll x = a[0]; 
    ll M = m[0]; 

    for (int i = 1; i < n; ++i) {
        // 合并第 i 个方程: M * t ≡ (a[i] - x) (mod m[i])
        ll A = M, B = m[i];
        ll C = (a[i] - x % B + B) % B; 
        ll t, y;
        ll gcd_val = exgcd(A, B, t, y);

        // 无解判定
        if (C % gcd_val != 0) {
            return -1;
        }

        // 计算最小正整数解 t
        ll mod = B / gcd_val;
        t = (ll)((int128)t * (C / gcd_val) % mod);
        t = (t % mod + mod) % mod;

        // 更新总解 x 和总模数 M (M 即为 lcm)
        x = x + t * M;
        M = M / gcd_val * B; 
        x = (x % M + M) % M;
    }

    return (x % M + M) % M;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<ll> a(n), m(n);
    for (int i = 0; i < n; ++i) {
        cin >> m[i] >> a[i];
    }

    ll ans = exCRT(n, a, m);
    cout << (ll)ans << "\n";

    return 0;
}

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