扩展中国剩余定理：轻松处理任意模数的同余方程组

你是否有过这样的经历？你和朋友一起分糖果，按照第一种分法，每人4颗会剩下2颗；按照第二种分法，每人6颗会剩下4颗。你想知道总共有多少颗糖。可是，4和6不互素，普通中国剩余定理（CRT）用不了。别急，扩展中国剩余定理（ExCRT）就是为此而生的！它不要求模数互素，能处理任何模数的同余方程组，只需要依次合并每个方程，就能得到最终答案（或者发现无解）。下面我们一步步搞懂它。

1. 数学原理和公式推导

1.1 为什么需要 ExCRT？

在上一节，我们学习了中国剩余定理（CRT），但它的前提是“所有模数两两互素”。很多实际问题中模数不一定互素，例如：

\begin{cases} x \equiv 2 \pmod{4} \\ x \equiv 4 \pmod{6} \end{cases}

4和6的最大公约数是2，不互素。如果我们强行用CRT，会发现无法求出逆元（因为 $M_i$ 和 $m_i$ 不互质）。这时就需要扩展中国剩余定理（ExCRT），它不要求模数互素，而是通过逐步合并方程来处理。

生活中的例子

假设你要去超市买鸡蛋，有两种包装方式：

每盒装4个鸡蛋，最后会多出2个（即鸡蛋总数除以4余2）。
每盒装6个鸡蛋，最后会多出4个（即鸡蛋总数除以6余4）。

鸡蛋的总数是多少？如果只有这两种规格，总数就是满足这两个同余方程的数。通过ExCRT，我们可以求出最小的正整数解。

1.2 两个方程的合并

假设我们有两个方程：

x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}

设 $d = \gcd(m_1, m_2)$ 。如果存在解，必须满足 $a_1 \equiv a_2 \pmod{d}$ ，即两个余数对 $d$ 同余。这个条件是解存在的必要条件，也是我们判断方程组是否有解的关键。

关键点小结

检查条件：(a2 - a1) % gcd(m1, m2) == 0。
解 $t$ 时，用扩展欧几里得求特解，然后取模到 $m_2/d$ 范围内。
新模数是两个模数的最小公倍数（lcm）。
新余数 = $a_1 + m_1 \times t_0$ ，最后取模新模数。

1.3 多个方程的依次合并

和上一节中处理同余方程组的方式一样，我们可以从第一个方程开始，不断用合并操作将方程两两合并，直到只有一个方程。如果中途任何一对合并失败（即 $d$ 不整除差值），则整个方程组无解。

生活类比：拼图游戏

想象你有几块拼图，每块拼图都告诉你在某个格子里的位置（余数）。但不同拼图的格子大小不同（模数）。如果某两块拼图给出的位置信息互相矛盾（比如一个说在格子2，另一个说在格子3，但两个格子的最小公共部分不允许这种矛盾），那这幅拼图就无解。否则，你可以先合并前两块，得到一个新的拼图块（更大格子的位置），再和第三块合并……最终只留下一块。

1.4 例子：不互素的方程组

例： $x \equiv 2 \pmod{4}, x \equiv 4 \pmod{6}$

$m_1=4, m_2=6, d=\gcd=2$ 。 $a_2 - a_1 = 4-2 = 2$ ，能被2整除，有解。
解方程 $4t \equiv 2 \pmod{6}$ 。先求 $d=2$ ，将方程两边除以 $d$ （注意模数也除以 $d$ ）： $(4/2)t \equiv (2/2) \pmod{6/2} \quad \Rightarrow \quad 2t \equiv 1 \pmod{3}$ 解 $2t \equiv 1 \pmod{3}$ ：2 的逆元 mod 3 是 2，所以 $t \equiv 2 \pmod{3}$ 。取 $t_0 = 2$ 。
新模数为 $\text{lcm}(4,6)=12$ ，新余数 $= a_1 + m_1 t_0 = 2 + 4 \times 2 = 10$ 。所以合并方程是 $x \equiv 10 \pmod{12}$ 。

验证：10 mod 4 = 2，10 mod 6 = 4，正确。最小正整数解是 10（取余 12）。

再一个例子：无解情况

考虑 $x \equiv 1 \pmod{2}, x \equiv 2 \pmod{4}$ 。

$m_1=2, m_2=4, d=2$ 。 $a_2 - a_1 = 2-1=1$ ，1不能被2整除，所以无解。
验证：满足第一个条件的数是奇数（1,3,5,7,...），满足第二个条件的数是除以4余2的数（2,6,10,...），没有公共数字，正确。

1.5 常见错误与注意事项

忘记检查整除条件：很多同学在合并时直接计算 $t$ ，但 $d$ 不整除差值时方程无解，必须提前返回无解。
模数缩小后取模错误：解 $t$ 时，得到的特解 $x_0$ 可能为负，需要调整到 $[0, m_2/d-1]$ 范围内。
溢出问题：计算新模数时， $m_1 \times m_2$ 可能超出整数范围，因此应该先除后乘：new_mod = m1 // d * m2（Python）或 m1 / d * m2（C++用 long long 先除）。
解的唯一性：当模数不互素时，解是模 $\text{lcm}$ 唯一的，不要误以为模乘积。

2. 编程实现思路

ExCRT 的编程实现其实就是一个不断合并的过程。我们可以写一个 merge 函数，它接受两个方程的参数（余数和模数），返回合并后的新方程（余数和模数），如果无解则返回错误标志。然后在主函数中循环调用 merge。

实现的关键在于用扩展欧几里得算法（exgcd）解线性同余方程。exgcd 可以同时求出最大公约数 $d$ 和一组特解 $(x,y)$ ，满足 $m_1 x + m_2 y = d$ 。我们只需要 $x$ 用于计算 $t_0$ 。

C++ 代码示例

#include <iostream>
#include <vector>
using namespace std;

// 扩展欧几里得，返回 gcd(a,b) 并设置 x,y 为 a*x + b*y = gcd
int exgcd(int a, int b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// 合并两个同余方程，使用 long long 避免溢出
bool merge(long long a1, long long m1, long long a2, long long m2,
           long long &a, long long &m) {
    long long x0, y0;                     // exgcd 所得的特解
    long long d = exgcd(m1, m2, x0, y0);  // d = gcd(m1, m2)
    long long diff = a2 - a1;             // 余数差
    if (diff % d != 0) return false;      // 无解
    
    // 解 k : m1 * k ≡ diff (mod m2)
    long long mod = m2 / d;               // 模数缩小后的值
    long long k = (diff / d) * x0 % mod;  // 注意 x0 可能为负
    if (k < 0) k += mod;                  // 调整到非负范围
    
    // 新模数为 lcm(m1, m2) = m1 / d * m2
    long long new_mod = m1 / d * m2;      // 先除后乘防止溢出
    // 新余数 = a1 + m1 * k (模 new_mod)
    long long new_rem = (a1 + m1 % new_mod * k % new_mod) % new_mod;
    if (new_rem < 0) new_rem += new_mod;  // 调整为非负
    
    a = new_rem;
    m = new_mod;
    return true;
}

// 扩展中国剩余定理：求解同余方程组，模数可不互素
// 返回 (结果余数, 结果模数) 或 (-1, -1) 表示无解
pair<long long, long long> exCRT(const vector<long long>& rem,
                                  const vector<long long>& mod) {
    long long result_rem = rem[0];   // 当前合并后的余数
    long long result_mod = mod[0];   // 当前合并后的模数
    for (size_t i = 1; i < rem.size(); ++i) {
        if (!merge(result_rem, result_mod, rem[i], mod[i],
                   result_rem, result_mod)) {
            return {-1, -1};  // 合并失败，无解
        }
    }
    return {result_rem, result_mod};
}

int main() {
    // 例1：x ≡ 2 (mod 4), x ≡ 4 (mod 6)
    vector<long long> rem = {2, 4};
    vector<long long> mod = {4, 6};
    auto [r, m] = exCRT(rem, mod);
    if (r == -1) cout << "无解" << endl;
    else cout << "解为: x ≡ " << r << " (mod " << m << ")" << endl; // 10 mod 12

    // 例2：x ≡ 5 (mod 10), x ≡ 3 (mod 6) 检查：gcd=2, diff=-2 能被2整除，有解。
    rem = {5, 3}; mod = {10, 6};
    tie(r, m) = exCRT(rem, mod);
    if (r == -1) cout << "无解" << endl;
    else cout << "解为: x ≡ " << r << " (mod " << m << ")" << endl; // 合并后 15 mod 30

    // 例3：无解情况 x ≡ 1 (mod 2), x ≡ 2 (mod 4)
    rem = {1, 2}; mod = {2, 4};
    tie(r, m) = exCRT(rem, mod);
    if (r == -1) cout << "无解" << endl;
    else cout << "解为: x ≡ " << r << " (mod " << m << ")" << endl; // 预期无解

    return 0;
}

Python 代码示例

def exgcd(a, b):
    """返回 (g, x, y) 满足 a*x + b*y = g"""
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = exgcd(b, a % b)
    # 回溯更新 x,y
    x = y1
    y = x1 - (a // b) * y1
    return (g, x, y)

def merge(a1, m1, a2, m2):
    """
    合并两个同余方程，返回 (new_rem, new_mod) 或 None（无解）
    """
    g, x0, _ = exgcd(m1, m2)      # g = gcd(m1,m2), x0 是特解
    diff = a2 - a1
    if diff % g != 0:              # 检查条件
        return None
    # 计算 t0 = (diff/g) * x0 mod (m2/g)
    mod = m2 // g
    k = (diff // g) * x0 % mod
    if k < 0:
        k += mod
    # 新模数 = lcm(m1, m2)
    new_mod = m1 // g * m2
    new_rem = (a1 + m1 * k) % new_mod
    return (new_rem, new_mod)

def exCRT(rem, mod):
    """扩展中国剩余定理，返回 (最终余数, 最终模数) 或 None"""
    r, m = rem[0], mod[0]
    for i in range(1, len(rem)):
        res = merge(r, m, rem[i], mod[i])
        if res is None:
            return None
        r, m = res
    return (r, m)

if __name__ == "__main__":
    # 例1
    rem = [2, 4]
    mod = [4, 6]
    res = exCRT(rem, mod)
    if res:
        r, m = res
        print(f"解为: x ≡ {r} (mod {m})")  # 10 mod 12
    else:
        print("无解")
    
    # 例2
    rem = [5, 3]
    mod = [10, 6]
    res = exCRT(rem, mod)
    if res:
        r, m = res
        print(f"解为: x ≡ {r} (mod {m})")  # 15 mod 30
    else:
        print("无解")
    
    # 例3 无解
    rem = [1, 2]
    mod = [2, 4]
    res = exCRT(rem, mod)
    if res:
        r, m = res
        print(f"解为: x ≡ {r} (mod {m})")
    else:
        print("无解")

exgcd 是 ExCRT 的核心工具。它求解 $a x + b y = \gcd(a,b)$ 的一组整数解 $(x,y)$ 。在合并函数中，我们用它求 $d = \gcd(m_1, m_2)$ 以及一个满足 $m_1 x_0 + m_2 y_0 = d$ 的 $x_0$ 。注意， $x_0$ 是 $m_1$ 的系数，正是我们解 $m_1 t \equiv \text{diff} \pmod{m_2}$ 需要的。

3.2 merge 函数详解

输入：两个方程的参数 $a1, m1$ 和 $a2, m2$ 。
步骤：
1. 计算 $d = \gcd(m1, m2)$ ，同时得到 $x0$ （这里不需要 $y0$ ，但 exgcd 会返回）。
2. 计算差值 diff = a2 - a1，检查 diff % d == 0。若否，返回无解。
3. 解线性同余方程：k = (diff / d) * x0 % (m2 / d)。注意这里模数已经除以 $d$ ，因为方程两边除以 $d$ 后模数也要除以 $d$ 。
4. 新模数 = m1 // d * m2（先除后乘避免溢出）。
5. 新余数 = (a1 + m1 * k) % new_mod，并调整为非负数。
输出：通过引用参数 a 和 m 返回新方程的余数和模数。

3.3 exCRT 函数

从第一个方程开始，依次与第 $i$ 个方程合并。如果某次合并返回 false，则整个方程组无解，返回 (-1, -1)（C++）或 None（Python）。

4. 新手容易犯的错误

溢出问题：在 C++ 中，计算 m1 * m2 可能超过 int 范围。务必使用 long long 并按 m1 / d * m2 顺序计算。Python 无此问题，但习惯上也可以这样写。
忘记取模：得到新余数后，要再次取模 new_mod，因为 a1 + m1 * k 可能很大。
负数处理：x0 和 k 可能为负，必须调整到 [0, mod-1] 范围内。C++ 中通过 if (k < 0) k += mod 处理。
输入顺序：exCRT 函数要求余数和模数向量长度相同，并且第一个元素对应第一个方程。下标从 0 开始。
混淆 CRT 与 ExCRT：当模数互素时，ExCRT 也能工作（结果与 CRT 一致），但计算效率稍低。推荐直接使用 ExCRT 处理所有情况，避免互素判断。

5. 与 CRT 的区别

适用范围：CRT 要求模数两两互素；ExCRT 没有此限制，可以处理不互素的情况。
唯一性：当互素时，解模 $M$ （乘积）唯一；不互素时，解模 $\text{lcm}$ 唯一（如果存在）。
算法复杂度：两者都是 $O(k \log M)$ 级别（通过扩展欧几里得）。

6. 总结

扩展中国剩余定理是处理同余方程组的终极工具。它不要求任何特殊条件，只需要一遍遍合并方程，直到得出最终答案或者发现无解。这个思想在数论和密码学（如RSA解密优化）中有重要应用。掌握了 ExCRT，你再也不用担心模数互不互素的问题了。

扩展中国剩余定理（ExCRT，模不互素）