深入解析线性同余方程与扩展中国剩余定理

核心逻辑与数学原理

线性同余方程

形如 $a \cdot x \equiv c \pmod b$ 的方程称为线性同余方程。该方程等价于二元一次不定方程：

$$a \cdot x + b \cdot y = c$$

根据裴蜀定理，方程有解的充要条件是 $\gcd(a, b) \mid c$。通过扩展欧几里得算法（$EXGCD$）可直接求解该方程。

中国剩余定理（CRT）

中国剩余定理用于求解一元线性同余方程组： $$\begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \ \vdots \ x \equiv a_k \pmod{m_k} \end{cases}$$ 适用条件：模数 $m_1, m_2, \dots, m_k$ 两两互质。

构造逻辑如下：

令总模数 $M = \prod_{i=1}^k m_i$。
令 $M_i = \frac{M}{m_i}$，即除 $m_i$ 以外其余所有模数的乘积。显然 $\gcd(M_i, m_i) = 1$。
令 $t_i = M_i^{-1}$ 为 $M_i$ 在模 $m_i$ 意义下的乘法逆元，即 $M_i \cdot t_i \equiv 1 \pmod{m_i}$。
方程组的通解结构为：

$$x = \sum_{i=1}^k a_i \cdot M_i \cdot t_i + k \cdot M \quad (k \in \mathbb{Z})$$

在模 $M$ 意义下，该方程组有唯一最小非负整数解。

算法推导与状态设计

扩展中国剩余定理（EXCRT）

当模数 $m_1, m_2, \dots, m_k$ 不满足两两互质时，传统 $CRT$ 构造法失效（逆元可能不存在）。必须采用数学归纳合并法，即拆解迭代。

假设已经求出了前 $i-1$ 个方程组成的同余方程组的一个特解为 $x_0$，令 $M = \text{lcm}(m_1, m_2, \dots, m_{i-1})$。则前 $i-1$ 个方程的通解形式为：

$$x = x_0 + k \cdot M \quad (k \in \mathbb{Z})$$

现在引入第 $i$ 个方程：$x \equiv a_i \pmod{m_i}$。将其带入通解形式中，转化为寻找一个整数 $k$，使得：

$$x_0 + k \cdot M \equiv a_i \pmod{m_i}$$

移项变形为标准的线性同余方程形式：

$$M \cdot k \equiv a_i - x_0 \pmod{m_i}$$

写成不定方程形式：

$$M \cdot k + m_i \cdot y = a_i - x_0$$

调用 $EXGCD$ 求解该方程。令 $g = \gcd(M, m_i)$。

若 $(a_i - x_0) \bmod g \neq 0$，则整个方程组无解。
若有解，由 $EXGCD$ 算出特解 $k_0$，通过步长 $t = \frac{m_i}{g}$ 将 $k$ 修正为最小非负整数：

$$k = (k_0 \cdot \frac{a_i - x_0}{g} \bmod t + t) \bmod t$$

更新特解 $x_0' = x_0 + k \cdot M$。更新总模数 $M' = \text{lcm}(M, m_i) = M \cdot \frac{m_i}{g}$。以此类推，迭代 $k-1$ 次即可合并所有方程。

C++ 标准源码

#include <iostream>
#include <vector>

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

// 扩展中国剩余定理 (EXCRT)
// 传入方程组：x \equiv a[i] (mod m[i])
// 注意：本模板内部已做防溢出乘法转换
long long excrt(const std::vector<long long> &a, const std::vector<long long> &m) {
    int n = a.size();
    long long M = m[0];
    long long x0 = a[0];

    for (int i = 1; i < n; ++i) {
        long long k0, y0;
        // 求解 M * k + m[i] * y = a[i] - x0
        long long c = ((a[i] - x0) % m[i] + m[i]) % m[i];
        long long g = exgcd(M, m[i], k0, y0);

        if (c % g != 0) return -1; // 无法整除，无解

        long long t = m[i] / g;
        // 使用 __int128_t 严防乘法爆发溢出 long long
        k0 = (long long)((__int128_t)k0 * (c / g) % t);
        k0 = (k0 + t) % t; // 映射到最小非负整数解

        x0 = x0 + k0 * M;
        M = M / g * m[i]; // 新的 lcm(M, m[i])
        x0 = (x0 % M + M) % M; // 保持特解在当前模数范围内
    }
    return x0;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    if (std::cin >> n) {
        std::vector<long long> a(n), m(n);
        for (int i = 0; i < n; ++i) {
            // 注意读入顺序：部分题目先读入模数，后读入余数
            std::cin >> m[i] >> a[i];
        }
        long long ans = excrt(a, m);
        std::cout << ans << "\n";
    }
    return 0;
}

NOIP 实战避坑指南

EXCRT 合并过程中的乘法溢出陷阱 在计算 k0 * (c / g) 以及 x0 + k0 * M 时，参与运算的变量级别通常已经是 $10^{12} \sim 10^{18}$ 级别。直接做乘法会瞬间发生 long long 截断，导致回溯出负数或错误的模数步长。必须强制转换为 __int128_t 进行中间运算，或者使用 $O(\log N)$ 的慢速乘（二进制平凑乘法）。
读入顺序的低级失误 洛谷 $CRT$ 模板题与 $EXCRT$ 模板题的输入格式中，模数 $m_i$ 和余数 $a_i$ 的先后顺序往往是相反的（一题先读 $m_i$ 再读 $a_i$，另一题先读 $a_i$ 再读 $m_i$）。盲目不看题面直接套用模板极其容易颠倒数组含义，导致输入数据直接卡死在 exgcd 内部。

经典 NOIP/洛谷真题

1. 洛谷 P3868 [TJOI2009] 猜数字

题意描述：给定两组整数 $a_1, a_2, \dots, a_k$ 和 $b_1, b_2, \dots, b_k$，已知 $\gcd(b_i, b_j) = 1$。求一个最小的正整数 $n$，使得对于所有的 $i$，都有 $(n - a_i) \bmod b_i = 0$。
问题本质：标准中国剩余定理（$CRT$）的变式应用。
核心解题思路：$(n - a_i) \bmod b_i = 0 \implies n \equiv a_i \pmod{b_i}$。由于题目明确指出了 $b_i$ 两两互质，这完全符合传统 $CRT$ 的使用条件。构造总乘积 $M$，算出各个分量后累加。需要注意的是，$a_i$ 可能为负数，读入时需转换成 (a[i] % b[i] + b[i]) % b[i]。

2. 洛谷 P4777 【模板】扩展中国剩余定理（EXCRT）

题意描述：求解一元线性同余方程组，其中模数 $m_i$ 不保证两两互质。数据规模 $n \le 10^5$，$\prod m_i \le 10^{18}$。
问题本质：不互质情况下的同余方程组增量合并。
核心解题思路：由于模数可能存在公约数，直接应用上述的归纳迭代法。每次将新的方程并入当前的特解中，若通过 $EXGCD$ 发现余数差无法整除最大公约数则输出无解。全程利用 __int128_t 护航乘法，避免中途爆掉数据范围。