中国剩余定理（CRT）：若模数 m₁, m₂, …, mₙ两两互质，则同余方程组在模 M = m₁m₂…mₙ 下有唯一解。记 Mᵢ = M / mᵢ，tᵢ = Mᵢ⁻¹ (mod mᵢ)，则解为：
x ≡ Σ aᵢ · Mᵢ · tᵢ (mod M)
扩展中国剩余定理（exCRT）：不要求模数两两互质。核心操作是"合并两个方程"：已知 x ≡ r₁ (mod m₁) 与 x ≡ r₂ (mod m₂)，设 g = gcd(m₁, m₂)，若 g ∤ (r₂ − r₁) 则方程组无解；否则合并为 x ≡ r (mod lcm(m₁, m₂))。重复 n − 1 次即可合并全部方程。
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
typedef __int128 i128; // 中间乘法用它防溢出
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1; y = 0; return a; }
ll g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
int main() {
int n; cin >> n;
vector<ll> a(n), m(n);
for (int i = 0; i < n; i++) cin >> a[i] >> m[i];
ll M = 1;
for (int i = 0; i < n; i++) M *= m[i]; // 总模数（注意是否会溢出）
i128 ans = 0;
for (int i = 0; i < n; i++) {
ll Mi = M / m[i]; // 除掉自己的那个模数
ll ti, y;
exgcd(Mi % m[i], m[i], ti, y); // 求 Mi 在 mod m[i] 下的逆元
ti = (ti % m[i] + m[i]) % m[i];
ans = (ans + (i128)(a[i] % m[i]) * Mi % M * ti) % M;
}
cout << (ll)(ans % M) << endl;
return0;
}
第三步：判无解。令 g = gcd(m₁, m₂)。由上一讲的判据，这个同余方程有解 ⟺ g | (r₂ − r₁)。若不能整除，整个方程组无解。
第四步：解出 t。三数同除 g 得 (m₁/g)·t ≡ (r₂−r₁)/g (mod m₂/g)，用 exgcd 求逆元解出 t 的最小非负解 t₀。
第五步：写出合并结果。r = r₁ + m₁·t₀，新模数 M′ = lcm(m₁, m₂) = m₁·m₂/g。最终 x ≡ r (mod M′)。
对 n 个方程，从第一个开始，依次把每个新方程"并"进当前结果 —— 一共合并 n − 1 次，就得到最终答案。复杂度 O(n log(max mᵢ))。
STEP 1初始化 r、M
STEP 2取下一个方程
STEP 3算 g 与逆元
STEP 4判 g | (ai − r)
STEP 5更新 r 与 M
STEP 6输出 r mod M
六步循环 n−1 次，互质与否都能处理，且能自动发现无解
动手算一遍：合并 x ≡ 1 (mod 4) 与 x ≡ 2 (mod 6)。
① 写 x = 1 + 4t；② 代入得 4t ≡ 1 (mod 6)；③ g = gcd(4, 6) = 2，而 1 不能被 2 整除 → 无解。直观上看：第一个条件要求 x 是奇数，第二个要求 x 是偶数，确实矛盾。
再看一个相容的例子：合并 x ≡ 3 (mod 4) 与 x ≡ 5 (mod 6)。
① x = 3 + 4t；② 4t ≡ 2 (mod 6)；③ g = gcd(4,6) = 2，2 | 2 ✓ 有解；④ 同除 2：2t ≡ 1 (mod 3)，即 t ≡ 2 (mod 3)（因为 2×2 = 4 ≡ 1），最小非负解 t₀ = 2；⑤ r = 3 + 4×2 = 11，新模数 lcm(4, 6) = 12。答案 x ≡ 11 (mod 12)。
验证：11 mod 4 = 3 ✓，11 mod 6 = 5 ✓。而 11、23、35、47、… 正是同时满足两式的全部整数。
6exCRT 的 C++ 模板 必背模板
C++exCRT 模板（模数不必互质，自动判无解）
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
typedef __int128 i128;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1; y = 0; return a; }
ll g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
// 把若干同余方程合并；失败（无解）时返回 falsebool excrt(vector<ll> &a, vector<ll> &m, ll &R, ll &M) {
R = 0; M = 1; // x ≡ 0 (mod 1)：单位元，等价于"无约束"for (size_t i = 0; i < a.size(); i++) {
ll A = M, B = m[i], C = ((a[i] - R) % B + B) % B; // 解 A*t ≡ C (mod B)
ll x, y;
ll g = exgcd(A, B, x, y);
if (C % g) return false; // 无解
ll Bg = B / g;
ll t = (ll)((i128)(C / g) % Bg * ((x % Bg + Bg) % Bg) % Bg);
// 更新：r = r + M*t，M = lcm(M, B)
R = (ll)((i128)R + (i128)(M % (M / g * Bg)) * t % (M / g * Bg));
R = (R % (M / g * Bg) + (M / g * Bg)) % (M / g * Bg);
M = M / g * Bg; // 新模数 = lcm
}
R = (R % M + M) % M;
return true;
}
int main() {
int n; cin >> n;
vector<ll> a(n), m(n);
for (int i = 0; i < n; i++) cin >> m[i] >> a[i]; // 注意读入顺序
ll R, M;
if (!excrt(a, m, R, M)) cout << "-1" << endl;
else cout << R << endl;
return0;
}
四个实现要点：① 初始值取 R = 0, M = 1（模 1 下所有数同余，相当于"还没有任何约束"）；② C = ((a[i] - R) % B + B) % B 必须归一化成非负，否则 C 为负时 C % g 的判断会出错；③ 逆元用的是 exgcd 返回的 x，它对应 A·x + B·y = g，所以 x 就是 A 在模 B 下的逆元候选（因为 A·x ≡ g (mod B)，但我们需要的是 A/g 在模 B/g 下的逆元，恰好也是 x 归一化后的值）；④ 中间乘法全部走 __int128。
案例案例1：P1495 曹冲养猪（CRT 模板题） 模板
题意：输入 n 组数据，第 i 组为 (mᵢ, aᵢ)，表示"每次数到 mᵢ 就重新开始，最后剩下 aᵢ 头猪"，也就是 x ≡ aᵢ (mod mᵢ)。保证 mᵢ 两两互质，求猪的最少头数（最小非负解）。
分析：这就是 CRT 的标准模板题。原始数据的乘积可能超出 long long，但因为题目保证答案在 long long 内，用 __int128 中转即可。
C++P1495 曹冲养猪 · 完整代码
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
typedef __int128 i128;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1; y = 0; return a; }
ll g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
int main() {
int n; cin >> n;
vector<ll> m(n), a(n);
for (int i = 0; i < n; i++) cin >> m[i] >> a[i];
ll M = 1;
for (int i = 0; i < n; i++) M *= m[i];
i128 ans = 0;
for (int i = 0; i < n; i++) {
ll Mi = M / m[i];
ll ti, y;
exgcd(Mi % m[i], m[i], ti, y); // Mi 在 mod m[i] 下的逆元
ti = (ti % m[i] + m[i]) % m[i];
ans = (ans + (i128)(a[i] % m[i]) * Mi % M * ti) % M;
}
cout << (ll)ans << endl;
return0;
}
▶ 运行结果
输入:
3
3 1
5 2
7 3
输出: 52
逐步展开:
M = 105
i=0: Mi = 35, 35 在 mod 3 下的逆元 = 2 → 1 * 35 * 2 = 70
i=1: Mi = 21, 21 在 mod 5 下的逆元 = 1 → 2 * 21 * 1 = 42
i=2: Mi = 15, 15 在 mod 7 下的逆元 = 1 → 3 * 15 * 1 = 45
求和: 70 + 42 + 45 = 157
取模: 157 mod 105 = 52 ✓
验算: 52 mod 3 = 1 ✓，52 mod 5 = 2 ✓，52 mod 7 = 3 ✓
三个易错点：① M *= m[i] 时若 n 较大可能溢出 long long（本题数据下安全，但养成用 __int128 的习惯）；② 求逆元时忘记把 Mi 对 m[i] 取模，exgcd 内部处理大数时容易出问题；③ 累加时没有及时取模，ans 膨胀。
案例案例2：P4777 【模板】扩展中国剩余定理（exCRT） 进阶模板
题意：给定 n 个同余方程 x ≡ bᵢ (mod aᵢ)，求最小非负整数解。不保证 aᵢ 两两互质，若方程组无解则需要输出错误信息。
分析：这是 exCRT 的模板题。核心就是"两两合并"，每次合并时判断 g | (bᵢ − R)。
C++P4777 exCRT · 完整代码
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
typedef __int128 i128;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1; y = 0; return a; }
ll g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
int main() {
int n; cin >> n;
ll R = 0, M = 1; // 当前答案：x ≡ R (mod M)for (int i = 0; i < n; i++) {
ll a, b; cin >> a >> b; // 新方程：x ≡ b (mod a)// 要解 M * t ≡ (b - R) (mod a)
ll C = ((b - R) % a + a) % a; // 归一化为非负
ll x, y;
ll g = exgcd(M, a, x, y);
if (C % g) { cout << "-1" << endl; return0; } // 无解
ll newM = M / g * a; // 新模数 = lcm(M, a)
ll ag = a / g;
ll inv = (x % ag + ag) % ag; // (M/g) 在 mod (a/g) 下的逆元
ll t = (ll)((i128)(C / g) % ag * inv % ag);
R = (ll)(((i128)R + (i128)M % newM * t) % newM);
M = newM;
}
R = (R % M + M) % M; // 归一到 [0, M)
cout << R << endl;
return0;
}
验证：17 mod 4 = 1 ✓，17 mod 5 = 2 ✓，17 mod 7 = 3 ✓。全部正确！
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
typedef __int128 i128;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1; y = 0; return a; }
ll g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
int main() {
vector<ll> a = {1, 2, 3}, m = {4, 5, 7};
ll M = 1;
for (ll mi : m) M *= mi;
i128 ans = 0;
for (int i = 0; i < 3; i++) {
ll Mi = M / m[i], ti, y;
exgcd(Mi % m[i], m[i], ti, y);
ti = (ti % m[i] + m[i]) % m[i];
ans = (ans + (i128)a[i] * Mi % M * ti) % M;
}
cout << (ll)ans << endl; // 17return0;
}
易错：求逆元时忘记取模得到负数；三项求和后忘记对 M 取模（会输出 577 而不是 17）。
题2综合编程 · 两方程合并
输入两个同余方程的参数 (m₁, r₁) 与 (m₂, r₂)，若相容则输出合并后的等价方程 x ≡ R (mod M)；若矛盾则输出 No Solution。
输入 n（n ≤ 10⁵）个同余方程 x ≡ rᵢ (mod mᵢ)，模数不保证两两互质，求最小非负整数解；若矛盾输出 −1。
数据范围：1 ≤ mᵢ ≤ 10¹²，0 ≤ rᵢ < mᵢ，保证答案在 long long 内。
查看参考答案
思路：维护当前合并结果 x ≡ R (mod M)，初值 R = 0、M = 1。每读入一个方程就做一次合并。
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
typedef __int128 i128;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1; y = 0; return a; }
ll g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
int main() {
int n; cin >> n;
ll R = 0, M = 1;
for (int i = 0; i < n; i++) {
ll m, r; cin >> m >> r;
ll C = ((r - R) % m + m) % m;
ll x, y;
ll g = exgcd(M, m, x, y);
if (C % g) { cout << "-1" << endl; return0; }
ll mg = m / g;
ll inv = (x % mg + mg) % mg;
ll t = (ll)((i128)(C / g) % mg * inv % mg);
ll newM = M / g * m;
R = (ll)(((i128)R + (i128)(M % newM) % newM * t) % newM);
M = newM;
}
cout << (R % M + M) % M << endl;
return0;
}
样例一（有解）：输入 3 / 6 4 / 8 6 / 9 7 → 输出 70。验证：70 mod 6 = 4 ✓、70 mod 8 = 6 ✓、70 mod 9 = 7 ✓。中间过程：先合并前两式得 x ≡ 22 (mod 24)，再与 x ≡ 7 (mod 9) 合并得 x ≡ 70 (mod 72)。
验证：23 mod 3 = 2 ✓，23 mod 5 = 3 ✓，23 mod 7 = 2 ✓。全部解为 x ≡ 23 (mod 105)。
易错：t₁ 算成 1（2×1 = 2 ≠ 1）；求和后忘记取模输出 233。
A2编程题
实现 CRT：输入 n 组 (mᵢ, aᵢ)，保证 mᵢ 两两互质，输出 x ≡ aᵢ (mod mᵢ) 的最小非负解。
查看参考答案
思路：直接套模板，注意用 __int128 做中间乘法。
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
typedef __int128 i128;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1; y = 0; return a; }
ll g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
int main() {
int n; cin >> n;
vector<ll> m(n), a(n);
for (int i = 0; i < n; i++) cin >> m[i] >> a[i];
ll M = 1;
for (int i = 0; i < n; i++) M *= m[i];
i128 ans = 0;
for (int i = 0; i < n; i++) {
ll Mi = M / m[i], ti, y;
exgcd(Mi % m[i], m[i], ti, y);
ti = (ti % m[i] + m[i]) % m[i];
ans = (ans + (i128)(a[i] % m[i]) * Mi % M * ti) % M;
}
cout << (ll)ans << endl;
return0;
}