中国剩余定理：互质构造与扩展同余合并

一、从暴力枚举到“状态打包”：一条条件是一整串数

引入场景：一个数除以 $3$ 余 $2$ ，除以 $5$ 余 $3$ ，除以 $7$ 余 $2$ 。求这个数。

暴力解法就是从 $2, 5, 8, 11, 14, 17, 20, 23 \dots$ 开始一个个往下试，直到找到 $23$ 同时满足三个条件。但模数一旦大起来，靠这样逐个试，可能还没找到答案，比赛就结束了。我们需要把“满足第一条的所有数”压成一个式子，再用下一条条件缩小范围。

物理视角的转换：写下 $x \equiv 2 \pmod 3$ ，说的不仅仅是 $x=2$ 这一个数，而是一个无穷的集合：

x = 2 + 3k, \quad k \in \mathbb{Z}

以后，我们把当前的全部合法解“打包”成一对数 $(r, M)$ ，表示：

x \equiv r \pmod M, \quad 0 \le r < M

其中

r

是最小非负解（起点），

M

是重复周期（间隔）。 注意边界：别把

r

说成“最小正解”。如果所有的条件都是余

0

，答案本来就是

0

。只有题目明确要求最小正整数解时，我们才会在最后给

0

加上一个完整周期

M

。

手工模拟一下降维合并：假设要把 $x \equiv 2 \pmod 3$ 和 $x \equiv 3 \pmod 5$ 合并。把 $x = 2 + 3k$ 暴力塞进第二条条件里：

2 + 3k \equiv 3 \pmod 5 \implies 3k \equiv 1 \pmod 5

此时我们要解出

k

。

3

在模

5

意义下的逆元是

2

（因为

3 \times 2 = 6 \equiv 1 \pmod 5

）。所以左右同乘

2

：

k \equiv 2 \pmod 5 \implies k = 2 + 5t

把它代回最开始的式子：

x = 2 + 3(2 + 5t) = 8 + 15t

看！两条条件被完美合并成了一条全新且长相完全一样的条件：

x \equiv 8 \pmod{15}

。

如果再把 $x \equiv 2 \pmod 7$ 合进来： $x = 8 + 15t \equiv 2 \pmod 7 \implies 1 + t \equiv 2 \pmod 7 \implies t \equiv 1 \pmod 7$ 于是 $t = 1 + 7q$ ，最终得到 $x = 8 + 15(1 + 7q) = 23 + 105q$ 。也就是： $x \equiv 23 \pmod{105}$ 。所以 $23, 128, 233$ 都是解。所谓唯一，是指模 $105$ 意义下只有一个余数，不是说整个整数世界只剩一个答案。

二、互质 CRT：各司其职的拼装魔法

如果模数 $m_1, m_2, \dots, m_n$ 两两互质，老祖宗留下的“中国剩余定理 (CRT)”给了一个非常优美的拼装公式。

令 $P = m_1 m_2 \dots m_n$ 。对于每一个条件，令 $P_i = P / m_i$ ，找 $P_i$ 在模 $m_i$ 下的逆元 $t_i$ 。那么 $P_i t_i$ 有个神奇的物理属性：对自己的模数余 $1$ ，对其他的模数统统余 $0$ 。 我们只要给它乘上要求的余数 $a_i$ ，它就只负责满足第 $i$ 条条件，完全不打扰别人！最后把所有贡献加起来：

x \equiv \sum_{i=1}^{n} a_i P_i t_i \pmod P

模数与余数	$P_i$	$P_i$ 在该模数下的余数	逆元 $t_i$	加入的贡献
$3,2$	$35$	$2$	$2$	$2 \times 35 \times 2 = 140$
$5,3$	$21$	$1$	$1$	$3 \times 21 \times 1 = 63$
$7,2$	$15$	$1$	$1$	$2 \times 15 \times 1 = 30$

合计 $233$ ，对 $105$ 取模，恰好得到 $23$ 。

求逆元用到的 exgcd，见《数学基础》·扩展欧几里得代码实现。

痛点与局限：这个公式太挑剔了。它强调“两两互质”，因为“所有模数的最大公约数为 1”还不够。比如 $6, 10, 15$ 的整体公约数是 $1$ ，但任意挑两个都不互质，直接套公式会当场罢工，求不出逆元。因此在实战中，我们更喜欢直接写一套“不管互不互质都能跑”的算法，也就是扩展中国剩余定理 (exCRT)。它本质上就是我们第一节手工模拟的“逐条合并法”。

三、不互质时的碰撞：为什么有时能合，有时不能？

遇到不互质的模数，先别慌，不互质 $\neq$ 无解。

场景 1：能够包容与合并 旧条件： $x \equiv 2 \pmod 6$ 。新条件： $x \equiv 5 \pmod 9$ 。令 $x = 2 + 6k$ ，代入第二条：

2 + 6k \equiv 5 \pmod 9 \implies 6k \equiv 3 \pmod 9

这里的

6

模

9

是没有逆元，不能强行做除法。但仔细看，左边、右边和模数，有一个最大公约数

3

！把它们整体除以 3，进行降维打击：

2k \equiv 1 \pmod 3

现在互质了！解得

k \equiv 2 \pmod 3

，即

k = 2 + 3t

。代回得到：

x = 2 + 6(2 + 3t) = 14 + 18t

。所以合并后的条件是

x \equiv 14 \pmod{18}

。注意这里的周期是

\text{lcm}(6, 9) = 18

，不是

6 \times 9 = 54

！如果你把周期写成

54

，虽然列出来的数仍可能满足条件，却会漏掉中间的合法解。

同余条件x≡2(mod 6)与x≡5(mod 9)的共同解为14、32、50等；相邻公共解相差lcm(6,9)=18，合并后为x≡14(mod 18)。

场景 2：彻底的矛盾 旧条件： $x \equiv 2 \pmod 6$ 。新条件： $x \equiv 4 \pmod 9$ 。代入得到： $6k \equiv 2 \pmod 9$ 。这意思是，存在整数 $y$ 使得 $6k + 9y = 2$ 。左边提取公因数是 $3(2k + 3y)$ ，永远是 $3$ 的倍数，但右边是 $2$ 。显然无解！ 物理意义解剖：其实不用列式也能发现冲突。第一条要求 $x$ 除以 $3$ 余 $2$ ，第二条要求它除以 $3$ 余 $1$ 。两条信息在公共部分上直接打架，任何数都无法同时满足。

四、exCRT 核心推导：把手推过程变成一次通用合并

假设我们手里攥着所有旧条件合并出来的结果： $x \equiv r \pmod M$ 。现在来了一个新条件： $x \equiv a \pmod m$ 。先别急着更新 $r$ ，我们需要用旧周期 $M$ 帮忙。

第一步，把旧条件展开： $x = r + Mk$ 。代入新条件：

r + Mk \equiv a \pmod m \implies Mk \equiv a - r \pmod m

为了方便，记

\Delta = a - r

。方程变成了

Mk \equiv \Delta \pmod m

。

第二步，找公约数探测冲突。求出 $g = \gcd(M, m)$ 。根据裴蜀定理，这个方程有解的充要条件是： $g \mid \Delta$ 。检查不通过就立即判无解，不需要继续往后尝试。

第三步，降维除以公约数。方程两边和模数同时除以 $g$ ：

\frac{M}{g} k \equiv \frac{\Delta}{g} \pmod{\frac{m}{g}}

此时，

\frac{M}{g}

和

\frac{m}{g}

互质，终于可以用扩展欧几里得 (exGCD) 强行求出

\frac{M}{g}

在模

\frac{m}{g}

下的逆元

u

。那么

k

的解就是：

k \equiv \frac{\Delta}{g} u \pmod{\frac{m}{g}}

第四步，更新灵魂状态 $(r, M)$ 。设 $q = \frac{m}{g}$ 。刚才求得的所有 $k$ 都能写成 $k_0 + qt$ 。代回原式就是： $x = r + M(k_0 + qt) = (r + Mk_0) + Mqt$ 。所以新周期就是 $L = M \times q$ （这其实就是 $\text{lcm}(M, m)$ ）。新的起点 $R$ 就是把求出的 $k$ 代入： $R = (r + Mk) \bmod L$ 。整个推导没有把解删掉，也没有凭空加入新解。

1. 💡 容易让你在考场上慌神的三个小情况

$\Delta = a - r$ 算出来是负数怎么办？ 比如旧条件是模 $5$ 余 $4$ ，新条件是模 $3$ 余 $1$ ，差值是 $-3$ 。这只说明两条起点的位置不同，照样检查整除、求逆元、规范余数即可，不能因为差值为负就判无解。
如果算出来的 $q = m/g = 1$ 怎么办？ 说明新模数 $m$ 整除旧周期 $M$ 。只要公共部分不冲突，新条件就已经被旧条件包含了，属于废话。代码对模 $1$ 规范化自然得到 $0$ ，不需要找一个“模一世界里的普通逆元”。
一开始还没有任何条件，怎么初始化？ 用 $(r, M) = (0, 1)$ 。因为“模 $1$ 余 $0$ ”允许所有整数。第一条条件和它合并后，就变成第一条本身，后面可以一直用同一个循环。

2. 扩欧 (exGCD) 返回的系数究竟是什么？

递归到底再回推，你会发现它解决的是 $ax + by = \gcd(a, b)$ 。在我们降维后的方程 $\frac{M}{g} u + \frac{m}{g} v = 1$ 里，丢进去跑一遍 exGCD 求出的那个系数 $u$ ，恰好就是 $\frac{M}{g}$ 的逆元。把余数替换回去，代码里的交换和减法就不再像一段背诵的咒语，它实实在在地帮你求出了步数 $k$ 需要的乘数。

五、核心代码实现：扩展 CRT 满分模板

【实战例题】 输入第一行 $n$ ( $1 \le n \le 10^5$ )；随后 $n$ 行，每行两个整数 m a，表示 $x \equiv a \pmod m$ 。约定每个模数为正、模数和余数均可用有符号 long long 读入；余数允许为负。题目保证全部模数的最小公倍数不超过 LLONG_MAX，即 $2^{63}-1$ 。 有解输出一行 r M，分别是最小非负解与全部解的周期；无解输出 -1。

复杂度分析：每次合并做一次扩欧，时间为 $O(\log V)$ ， $V$ 可取整个过程最大的模数或周期；总时间 $O(n \log V)$ 。条件可以边读边合，不需要把所有同余式存下来。

#include<bits/stdc++.h>
#define int long long
using namespace std;
using i128 = __int128;

// 将任意整数 x 规范化到 [0, m-1]
i128 norm(i128 x, i128 m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}

// 扩展欧几里得：返回最大公约数，并求出系数 x, y
int exgcd(int a, int b, i128 &x, i128 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    i128 u, v;
    int g = exgcd(b, a % b, u, v);
    x = v;
    // 回推：当前第一系数减去商乘第二系数
    y = u - (i128)(a / b) * v;
    return g;
}

void solve() {
    int n;
    if (!(cin >> n)) return;
    
    // 初始化无限制状态：模 1 余 0
    int r = 0, M = 1; 
    
    for (int i = 1; i <= n; i++) {
        int m, raw;
        cin >> m >> raw;
        
        int a = (int)norm((i128)raw, m);
        i128 u, v;
        int g = exgcd(M, m, u, v);
        
        // 冲突检测
        i128 delta = (i128)a - r;
        if (delta % g != 0) {
            cout << -1 << '\n';
            return;
        }
        
        // 降维求步数 k
        int q = m / g;
        i128 k = norm(delta / g, q) * norm(u, q) % q;
        
        // 更新灵魂状态 (r, M)
        // 输入保证最终 lcm <= LLONG_MAX，各步周期也不会超过它
        i128 L = (i128)M * q;
        i128 R = norm((i128)r + (i128)M * k, L);
        
        r = (int)R;
        M = (int)L;
    }
    cout << r << ' ' << M << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

1. 细节避坑：三处类型转换，不是装饰

看看 delta：先把 $a$ 转成宽整数，再减 $r$ 。再看周期 L = (i128)M * q：必须先转宽整数再乘。不能写成用 int（long long）算完 M * q，最后才把已经溢出成垃圾数据的数字交给宽变量。计算 k 时，中间乘法 $q \le 2^{63}-1$ ，其乘积刚好小于 $2^{126}$ ，有符号 128 位整数装得下。这里用 __int128 是因为它刚好涵盖了本题的数据边界，不是说有了宽类型就可以随便连乘三四个数。最后把 $R, L$ 塞回 int (long long) 也是依赖于题目给出的范围保证。

六、扩展变式一：带系数的同余方程怎么合并？

痛点场景：题目给出的不是干净的 $x \equiv r \pmod M$ ，而是带有系数的线性同余方程： $a \cdot x \equiv b \pmod m$ 。例如 $4x \equiv 6 \pmod{10}$ 。我们的 exCRT 模板是不吃系数的，必须先把它“剥干净”。

推导与降维：根据同余的物理意义， $a \cdot x \equiv b \pmod m$ 等价于存在整数 $y$ 使得 $a \cdot x + m \cdot y = b$ 。又遇到了熟悉的裴蜀定理！设 $g = \gcd(a, m)$ 。

冲突检测：如果 $g \nmid b$ ，说明该方程本身无解，直接结束。
整体降维：两边同除以 $g$ ，得到 $\frac{a}{g} x \equiv \frac{b}{g} \pmod{\frac{m}{g}}$ 。
消去系数：此时 $\frac{a}{g}$ 和 $\frac{m}{g}$ 必然互质。我们可以使用扩展欧几里得求出 $\frac{a}{g}$ 在模 $\frac{m}{g}$ 意义下的逆元 $u$ 。左右同乘 $u$ ，就得到了干净的标准形态：
$x \equiv u \cdot \frac{b}{g} \pmod{\frac{m}{g}}$

手算小例子： $4x \equiv 6 \pmod{10}$ 。

求 $\gcd(4, 10) = 2$ ，能整除 $6$ 。
整体除以 $2$ ，降维成 $2x \equiv 3 \pmod 5$ 。
$2$ 模 $5$ 的逆元是 $3$ （因为 $2 \times 3 = 6 \equiv 1 \pmod 5$ ）。
左右同乘 $3$ ，得到 $x \equiv 9 \equiv 4 \pmod 5$ 。接下来，直接把起点 $r=4$ ，周期 $M=5$ 扔进前文的 exCRT 模板里合并即可。

代码片段（接在第五节的输入阶段）：下面假设读入的是 a b m，且系数 a、模数 m 为正；先把带系数条件化成 new_r, new_m，再送入原来的合并逻辑。这个片段复用前文的 exgcd 和 norm。

具体接法：把第五节循环中的 int m, raw;、cin >> m >> raw; 和 int a = ...norm...; 换成 int a, b, m; cin >> a >> b >> m;，然后放入下面片段。结束时 a 已是规范余数，直接接回 i128 u, v; 与后面的合并过程，不再重复声明 a。

int new_m, new_r;
{
    i128 u, v;
    int g = exgcd(a, m, u, v);
    if (b % g != 0) {
        cout << -1 << '\n';
        return;
    }
    new_m = m / g;
    // u 是 a/g 的逆元，先规范化，再计算新余数
    new_r = (int)(norm(u, new_m) * norm(b / g, new_m) % new_m);
}
// 现在 x ≡ new_r (mod new_m)，接回第五节的冲突检测与合并
m = new_m;
a = new_r;

七、扩展变式二：从同余状态提取区间精确解与计数

同余合并结束时，我们拿到的是“最小非负解 $r$ ”和“循环周期 $M$ ”。但题目常常会在最后进一步问：求给定区间 $[L, R]$ 里的最小解，或者区间内有多少个合法解。

以下只讨论非负区间 $0\le L\le R$ 。沿用第五节的 i128，计算跨周期的步数和答案时用宽整数，避免贴近 long long 上限时加法溢出。

1. 求不小于 $L$ 的最小解

如果 $r \ge L$ ，答案就是 $r$ 。如果 $r < L$ ，我们需要在 $r$ 的基础上加若干个周期 $M$ ，恰好跨越 $L$ 。跨越的距离是 $L - r$ ，周期步长是 $M$ ，需要走的步数就是 $\lceil \frac{L-r}{M} \rceil$ 。在 C++ 中，对于正整数的向上取整经典写法是 (距离 + 步长 - 1) / 步长。

i128 get_min_solution(int r, int M, int L) {
    if (r >= L) return r;
    i128 steps = ((i128)L - r + M - 1) / M;
    return r + steps * M;
}

2. 求区间 $[L, R]$ 内解的个数

利用前缀和思想，直接转化为“求 $\le R$ 的解的个数”减去“求 $\le L-1$ 的解的个数”。对于任意上限 $X$ ，满足 $r + k \cdot M \le X$ 且 $k \ge 0$ 的个数是多少？解不等式得到 $k \le \lfloor \frac{X - r}{M} \rfloor$ 。因为步数 $k$ 是从 $0$ 开始走的，所以包含的解数是 $k + 1$ 。如果 $X < r$ ，个数自然为 $0$ 。

i128 count_solutions(int r, int M, int X) {
    if (X < r) return 0;
    return ((i128)X - r) / M + 1;
}

// 区间 [L, R] 的解数
i128 query_range(int r, int M, int L, int R) {
    if (L > R) return 0;
    return count_solutions(r, M, R) - count_solutions(r, M, L - 1);
}

两个函数返回 i128，不能直接交给 cout。确认答案在 long long 范围内时可输出 (long long)ans；超过这个范围就要写 i128 的逐位输出函数。

八、模板能力的边界：当 LCM 撑爆数据类型怎么办？（选学）

第五节用 __int128 保护中间乘法，但最后会把周期存回 long long。所以它的范围保证仍是 LCM 不超过 LLONG_MAX，不是“只要 128 位装得下就能一直合”。一旦超出这个保证，不能照抄模板里的 M=(int)L。

实战防崩技巧：极简上限截断法 仔细审题，这种题目往往会给出一个最终解的上限 $N$ （比如求 $10^{18}$ 范围内满足条件的数）。如果在某一步合并后，当前的周期 $M$ 已经严格大于 $N$ ，这意味着什么？这意味着在 $[0, N]$ 这个有限的范围里，最多只能容纳一个解，并且这个解只能是当前的最小非负解 $r$ （前提是 $r \le N$ ）。

在上限 $0\le N\le\text{LLONG\_MAX}$ 的这类题里，应当在算出宽整数 L,R 后、转回 long long 之前判断 L>N。若 R>N，区间内已经无解；否则只保留候选 R，不用再计算后续周期。剩下的同余条件，直接拿着这个唯一的独苗去验证：

如果对于所有剩下的条件，都有 R % m[i] == norm(a[i],m[i])，那 R 就是唯一答案。
只要有一个条件验证失败，说明在上限 $N$ 以内无解。

这只适用于有明确非负上限的版本；第五节要求输出完整周期，不能用这个截断代替原任务。没有这种上限时，再考虑更宽的存储或高精度。

九、练习：先预测，再运行

写完模板后，别急着乱交，用这几组边角料抓一抓公式里的符号错误。

第一组：互质标准局

预期输出：23 105。不用重新推公式，检查每次合并后的 $(r,M)$ 是否依次为 $(2,3), (8,15), (23,105)$ 。

第二组：矛盾打架局

2
6 2
9 4

预期输出：-1。请在执行扩欧之前，先在纸上写出它们在模 $3$ 意义下为什么发生矛盾。

第三组：负余数规范局

2
5 -1
3 1

预期输出：4 15。 $-1 \pmod 5$ 就是 $4$ 。最小非负答案不需要沿着负数方向找，norm 会把它拉正。

第四组：被包含的废话条件

预期输出：8 12。后两条没有增加任何实质性限制，不能把周期无缘无故再乘一遍。

第五组：同余有解，区间里却未必有

已经算出 $x\equiv14\pmod{18}$ 。先预测：不早于 $50$ 的第一个解是多少？区间 $[51,60]$ 内有几个解？再调用第七节的两个函数检查。

答案分别是 $50$ 、 $0$ 。注意区分“这一段没有解”和“同余条件互相矛盾”。

中国剩余定理