typedef long long ll;
// 求 a·x + b·y = gcd(a, b) 的一组整数解，返回 gcd
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { // 边界：a·1 + 0·0 = a
x = 1; y = 0;
return a;
}
ll x1, y1;
ll g = exgcd(b, a % b, x1, y1); // 先递归求出下一层的解
x = y1; // x = y'
y = x1 - (a / b) * y1; // y = x' - ⌊a/b⌋·y'return g;
}
也可以直接把 x、y 作为"下一层的解"复用，省掉临时变量 —— 这是最常见的写法：
C++exgcd · 写法二：原地复用引用（推荐）
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); // 此时 x, y 是下一层的解 (x', y')
ll t = x; // 暂存 x'，因为马上要覆盖 x
x = y; // x = y'
y = t - (a / b) * y; // y = x' - ⌊a/b⌋·y'return g;
}
把同余式 a·x ≡ b (mod m) 翻译成等式，就是存在整数 y 使 a·x + m·y = b。于是裴蜀定理直接给出判据：
1
🔍
算 g = gcd(a, m)
这是整个流程的第一步，也是判断有无解的唯一依据。
2
🚫
若 g ∤ b → 无解
左边永远是 g 的倍数，右边不是，方程不可能成立。
3
➗
三数同除 g
令 A = a/g、B = b/g、M = m/g。此时 gcd(A, M) = 1，方程化为 A·x ≡ B (mod M)。
4
🔁
exgcd 求系数
解 A·x + M·y = 1，得到 x′（A 在模 M 下的逆元）。
5
✂️
拼出最小正整数解
x = B · x′，再对 M 取模归一：((x % M) + M) % M。
6
🧩
写出全部 g 个解
模 m 意义下共有 g 个解，它们是 x、x + M、x + 2M、…、x + (g−1)M。
为什么模 m 下恰有 g 个解？因为通解 x = x₀ + M·k 的步长是 M = m/g，在长度为 m 的一个周期内恰好能放 g 个互不同余的值。
上图的例子 4x ≡ 2 (mod 6) 值得仔细体会：它在模 6 下有两个解，而在约简后的模 3 下只有一个解 x ≡ 2。这正是"g 个解"的由来 —— 把模数缩小 g 倍后，解从一个"长"成 g 个。
案例案例1：exgcd 模板题 —— 求 ax + by = gcd(a, b) 的一组解 基础模板
题意：输入两个正整数 a、b（1 ≤ a, b ≤ 10¹⁸），输出 gcd(a, b) 以及一组满足 a·x + b·y = gcd(a, b) 的整数解 (x, y)。
C++exgcd 模板题 · 完整代码
#include<bits/stdc++.h>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 g = exgcd(b, a % b, x, y);
ll t = x; // 暂存 x'
x = y; // x = y'
y = t - (a / b) * y; // y = x' - ⌊a/b⌋·y'return g;
}
int main() {
ll a, b; cin >> a >> b;
ll x, y;
ll g = exgcd(a, b, x, y);
cout << g << " " << x << " " << y << endl;
return0;
}
要点提醒：① 这里的 a、b 可以到 10¹⁸，但 a / b 与乘法 (a/b) * y 都在 long long 范围内（因为 |y| ≤ b/g ≤ b，而 (a/b)*|y| ≤ a），一般不会溢出；② 若题目要求"非负系数"或"最小绝对值解"，需要额外做一次归一化；③ exgcd 得到的解是不唯一的，不同实现方式可能给出不同的 (x, y)，只要是合法解就会被评测机接受（Special Judge 题）。
案例案例2：P1082 [NOIP2012 提高组] 同余方程 真题
题意：求关于 x 的同余方程 a·x ≡ 1 (mod b) 的最小正整数解。输入保证有解，2 ≤ a, b ≤ 2×10⁹。
分析：题目说"保证有解"，也就是 gcd(a, b) = 1。方程等价于 a·x + b·y = 1，直接 exgcd 求出 x₀，再归一到 [1, b] 区间即可。注意本题不能用费马小定理 —— b 不一定是素数。
C++P1082 同余方程 · 完整代码
#include<bits/stdc++.h>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 g = exgcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - (a / b) * y;
return g;
}
int main() {
ll a, b; cin >> a >> b;
ll x, y;
exgcd(a, b, x, y); // a*x + b*y = gcd(a,b) = 1
x = (x % b + b) % b; // 归一到 [0, b)if (x == 0) x = b; // 求"正整数"解，0 要换成 b
cout << x << endl;
return0;
}
三个易错点：① 忘记写 (x % b + b) % b，exgcd 返回的 x 可能是负数（本例中 x₀ = −3），直接输出会被判错；② 用费马小定理写 qpow(a, b - 2, b)，但 b 不是素数，答案全错；③ a / b 里的除法写成浮点。
顺带一提：本题还有一个 O(b) 的线性递推解法，但 b 到 2×10⁹ 时会超时；而 exgcd 只需 O(log b) 次运算，是本题唯一稳妥的做法。
案例案例3：P1516 青蛙的约会 经典应用
题意：两只青蛙在一条首尾相接的数轴上（长度为 L 的环）跳跃。青蛙 A 从 x 出发，每次跳 m 米；青蛙 B 从 y 出发，每次跳 n 米。它们同向同速起跳，问跳多少次后能相遇？若永远不能相遇输出 Impossible。
建模：跳 t 次后 A 在 (x + m·t) mod L，B 在 (y + n·t) mod L。相遇即两者相等：
(m − n)·t ≡ y − x (mod L)
这是标准的一次同余方程。设 a = m − n、c = y − x、g = gcd(a, L)：若 g ∤ c 输出 Impossible；否则把 a、c、L 同除 g，用 exgcd 求出 t₀，再归一到最小正整数。
C++P1516 青蛙的约会 · 完整代码
#include<bits/stdc++.h>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 g = exgcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - (a / b) * y;
return g;
}
int main() {
ll x, y, m, n, L;
cin >> x >> y >> m >> n >> L;
ll a = m - n, c = y - x;
if (a < 0) { a = -a; c = -c; } // 把系数转成非负，便于取模
ll x0, y0;
ll g = exgcd(a, L, x0, y0); // a*x0 + L*y0 = gif (c % g != 0) { // 裴蜀定理判无解
cout << "Impossible" << endl;
return0;
}
ll t = L / g; // t 的周期// 特解 ×(c/g)，再归一到 [0, t)
ll k = (c / g) % t;
ll ans = (ll)((__int128)((x0 % t + t) % t) * ((k % t + t) % t) % t);
if (ans == 0) ans = t; // 要求正整数次数
cout << ans << endl;
return0;
}
#include<bits/stdc++.h>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 g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
int main() {
ll a, m; cin >> a >> m;
ll x, y;
ll g = exgcd(a, m, x, y);
if (g != 1) { cout << "-1" << endl; return0; }
ll inv = (x % m + m) % m;
if (inv == 0) inv = m; // 一般 m > 1 时不会发生
cout << inv << endl;
return0;
}
易错：忘记判 g != 1；归一化漏写 +m；把 exgcd(a, m, x, y) 写成 exgcd(m, a, x, y)（此时 x 是 m 的系数，不是逆元）。
题3综合编程 · 解的结构
输入 a, b, m（1 ≤ a, b, m ≤ 10⁹），解同余方程 a·x ≡ b (mod m)：若 g = gcd(a, m) 不整除 b 输出 No Solution；否则先输出解的个数，再按升序输出模 m 下的全部 g 个解。
查看参考答案
思路：① g = gcd(a, m)；② 若 b % g ≠ 0 → 无解；③ 三数同除 g，得到 A·x ≡ B (mod M)，其中 gcd(A, M) = 1；④ 用 exgcd 求 A 在模 M 下的逆元 invA，得 x₀ = B · invA mod M；⑤ 全部解为 x₀ + k·M（k = 0 … g−1）。
#include<bits/stdc++.h>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 g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
int main() {
ll a, b, m; cin >> a >> b >> m;
ll x, y;
ll g = exgcd(a, m, x, y); // a*x + m*y = gif (b % g != 0) { cout << "No Solution" << endl; return0; }
ll A = a / g, B = b / g, M = m / g;
// 用上一次的 x（即 A 的逆元候选）直接求
ll invA = (x % M + M) % M; // A * invA ≡ 1 (mod M)
ll x0 = (ll)((__int128)(B % M) * invA % M);
cout << g << endl;
for (ll k = 0; k < g; k++) cout << x0 + k * M << " ";
cout << endl;
return0;
}
为什么恰好是 g 个解？因为通解的步长是 M = m/g，在一个长度为 m 的完整模周期内，步长为 m/g 的等差数列恰好有 g 个元素。
易错：解出来直接输出 x₀ 就完事（漏掉其余的 g−1 个解）；忘记按升序输出（x₀ 本身就在 [0, M) 里，所以 x₀ + kM 天然递增）；当 g = m（即 a 是 m 的倍数）且 b % m == 0 时，M = 1，这时全部 m 个解是 0, 1, …, m−1，循环会输出 m 个值 —— 数据范围下 m ≤ 10⁹ 时这种情形要小心 TLE，但本题目保证 m 较小或会出现这种边界时需特判。
模块 04
总结提升
把本讲的公式、模板、判据收拢成一张表，再用三个拓展案例把它推到更远处。
📌核心要点一览
知识点
结论 / 公式
关键前提
裴蜀定理
a·x + b·y = c 有整数解 ⟺ gcd(a,b) | c
a、b 不全为 0
互质判据
gcd(a,b) = 1 ⟺ ∃ x,y 使 ax + by = 1
—
gcd 的表示
gcd(a,b) = {ax+by>0} 中的最小值
—
exgcd 回代
x = y′，y = x′ − ⌊a/b⌋·y′
gcd(a,b) = gcd(b, a mod b)
exgcd 边界
b = 0 时 x = 1, y = 0，返回 a
—
exgcd 复杂度
O(log max(a, b))
与辗转相除法同阶
通解（k ∈ ℤ）
x = x₀ + (b/g)k，y = y₀ − (a/g)k
g = gcd(a,b)，(x₀,y₀) 为特解
最小正整数解
((x₀ % t) + t) % t，为 0 则取 t
t = b/g
同余方程有解
a·x ≡ b (mod m) 有解 ⟺ gcd(a,m) | b
—
解的数量
模 m 下恰有 g = gcd(a,m) 个解
先三数同除 g 再求解
exgcd 求逆元
inv(a) = x₀ mod m
gcd(a,m) = 1，m 可为合数
两方程合并
x ≡ r₁ (mod m₁)、x ≡ r₂ (mod m₂) → x ≡ r (mod lcm)
用 exgcd 解 m₁t ≡ r₂−r₁ (mod m₂)
⌨️本讲必背模板（一份可直接抄的代码）
C++exgcd 工具箱：求 gcd、求逆元、解同余方程、求最小正整数解
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
// ① 扩展欧几里得：解 a*x + b*y = gcd(a, b)，返回 gcd
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;
}
// ② 任意模数下的逆元（要求 gcd(a, m) = 1），失败返回 -1
ll inv(ll a, ll m) {
ll x, y;
if (exgcd(a, m, x, y) != 1) return -1;
return (x % m + m) % m;
}
// ③ 解同余方程 a*x ≡ b (mod m)，返回 {解的个数, 最小非负解}
pair<ll, ll> solveCong(ll a, ll b, ll m) {
ll x, y;
ll g = exgcd(a, m, x, y);
if (b % g) return {0, -1}; // 无解
ll A = a / g, B = b / g, M = m / g;
ll invA = (x % M + M) % M; // A 在 mod M 下的逆元
ll x0 = (ll)((__int128)(B % M) * invA % M);
return {g, x0}; // 全部解：x0 + k*M, k = 0..g-1
}
// ④ 求 ax + by = c 的最小正整数解 x，返回 -1 表示无解
ll minPosX(ll a, ll b, ll c) {
ll x, y;
ll g = exgcd(a, b, x, y);
if (c % g) return -1;
ll B = b / g, C = c / g;
ll r = (ll)((__int128)x * C % B + B) % B;
if (r == 0) r = B;
return r;
}
int main() {
cout << inv(3, 10) << endl; // 7
cout << minPosX(12, 5, 1) << endl; // 3auto [cnt, x0] = solveCong(4, 2, 6);
cout << cnt << " " << x0 << endl; // 2 2return0;
}
思考2：exgcd 的递归深度是多少？为什么说它"几乎不会爆栈"？如果 a、b 取到 long long 的上界，最深能递归多少层？
查看参考答案
结论：递归深度与辗转相除法的步数相同，是 O(log(min(a, b))) 级别。
为什么只有对数级：每次递归参数变成 (b, a mod b)，而 a mod b < b；更关键的是可以证明 a mod b < a / 2。因为若 b ≤ a/2，则 a mod b < b ≤ a/2；若 b > a/2，则 a mod b = a − b < a/2。所以每两层参数至少减半，深度是 O(log a)。
最坏情形：当 a、b 是相邻斐波那契数时步数最多。F(45) ≈ 1.13×10⁹，F(46) 已超过 long long 能容纳的一半量级附近；取到 9.2×10¹⁸ 时，对应的斐波那契下标约在 90 左右。所以 深度不会超过约 90 层。
实现 exgcd，输入 a、b，输出 gcd(a, b) 与一组满足 ax + by = gcd(a, b) 的整数解。
查看参考答案
思路：直接套模板，注意引用参数与临时变量。
#include<bits/stdc++.h>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 g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
int main() {
ll a, b, x, y; cin >> a >> b;
ll g = exgcd(a, b, x, y);
cout << g << " " << x << " " << y << endl;
return0;
}
样例：输入 35 12 → 输出 1 -1 3。验算：35×(−1) + 12×3 = 1 ✓
易错：参数传值而非引用；递归调用写成 exgcd(a % b, b, x, y)（参数顺序反了）。
A3编程题
用 exgcd 求 a 在模 m 下的逆元（1 ≤ a, m ≤ 10⁹，保证 gcd(a, m) = 1）。
查看参考答案
思路：逆元满足 ax + my = 1，exgcd 求出的 x 归一到 [0, m) 就是答案。
#include<bits/stdc++.h>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 g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
int main() {
ll a, m, x, y; cin >> a >> m;
exgcd(a, m, x, y);
cout << (x % m + m) % m << endl;
return0;
}
易错：充分性方向里忘记说明"d 是正整数"（若允许 d = −1 会推出 d = ±1）；或者用"a、b 都能被 d 整除"就直接断定 d = 1，缺少"d | 1"这一步。
🟡 B组 · 提高（4题）
B1综合编程
输入 a、b、c（均为 int 范围内正整数），判断 ax + by = c 是否有整数解，若有输出最小正整数 x 及对应的 y。
查看参考答案
思路：g = exgcd(a, b) → 判 c % g；否则把特解乘 c/g，再把 x 对 b/g 取模归一。
#include<bits/stdc++.h>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 g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
int main() {
ll a, b, c, x, y; cin >> a >> b >> c;
ll g = exgcd(a, b, x, y);
if (c % g) { cout << "No Solution" << endl; return0; }
ll B = b / g, C = c / g;
ll xm = (ll)((__int128)x * C % B + B) % B;
if (xm == 0) xm = B;
ll ym = (c - a * xm) / b;
cout << xm << " " << ym << endl;
return0;
}
【P1082 同余方程】输入 a、b（2 ≤ a, b ≤ 2×10⁹，保证有解），输出 ax ≡ 1 (mod b) 的最小正整数解。
查看参考答案
思路：标准 exgcd 求逆元。因为题目保证有解，所以 gcd(a, b) = 1，直接 exgcd 后归一化。
#include<bits/stdc++.h>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 g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
int main() {
ll a, b, x, y; cin >> a >> b;
exgcd(a, b, x, y);
cout << (x % b + b) % b << endl;
return0;
}
样例：输入 3 10 → 7；输入 2 3 → 2。
考点：exgcd 求逆元 + 负数归一化。
易错：用费马小定理（b 不是素数，直接 WA）；输出未归一化的负数。
B3分析题
为什么 exgcd 的递归深度是对数级的？请给出严格证明，并说明最坏情况出现在什么输入上。
查看参考答案
核心引理：对任意正整数 a ≥ b，有 a mod b < a / 2。
证明：分两种情形。① 若 b ≤ a/2，则 a mod b < b ≤ a/2。② 若 b > a/2，则 a = 1·b + (a − b)，其中 a − b < a − a/2 = a/2，所以 a mod b = a − b < a/2。两种情形都成立。∎
推论：一次递归调用 exgcd(a, b) 变成 exgcd(b, a mod b)。看两次递归：a → b → (a mod b)。由引理，a mod b ≤ a/2，所以每两层第一个参数至少减半。因此总层数是 O(log a)。
最坏输入：相邻的两个斐波那契数。设 a = F(n+1)、b = F(n)，则 a mod b = F(n−1)，每层只缩小到前一个斐波那契数，缩减比例约为黄金分割比 0.618，是所有输入中下降最慢的。
具体数值：F(88) ≈ 1.1×10¹⁸，F(89) ≈ 1.8×10¹⁸，都在 long long 范围内。所以取 a = F(89)、b = F(88) 时递归深度约 88 层 —— 这就是 long long 数据下的最坏情形。
公式推导：由 p = ⌊p/i⌋·i + (p mod i)，两边对 p 取模得 0 ≡ ⌊p/i⌋·i + (p mod i)，即 ⌊p/i⌋·i ≡ −(p mod i)。两边同乘 inv(i)·inv(p mod i)，整理得 inv(i) ≡ −⌊p/i⌋·inv(p mod i)，写成非负形式就是代码里的 (p − p/i)。
易错：把递推公式写成 inv[i] = (p - p/i) * inv[i % p]（下标错了，应是 p % i）；忘记 1 % p 处理 p = 1 的边界；数组用 int 存但在中间乘法时溢出。
🔴 C组 · 挑战（4题）
C1初赛选择题
下列说法正确的有几个？ ① 方程 6x + 9y = 8 有整数解 ② gcd(a, b) 一定可以表示成 ax + by 的形式（x, y 为整数） ③ 同余方程 ax ≡ b (mod m) 在模 m 下若有解，则解的个数等于 gcd(a, m) ④ 若 a·x + b·y = c 有一组整数解，则它有无穷多组整数解（a、b 均非零）
A. 1 B. 2 C. 3 D. 4
查看参考答案
答案：C（3 个）
①错误：gcd(6, 9) = 3，而 3 ∤ 8，由裴蜀定理无整数解。
②正确：这正是裴蜀定理的直接结论。
③正确：设 g = gcd(a, m)，有解时通解为 x = x₀ + (m/g)·k，在模 m 的一个周期内恰有 g 个不同的值。
与目标形式 a·x + b·y = g 对照，取 x = y′、y = x′ − ⌊a/b⌋·y′ 即得 a·x + b·y = g。而这两个赋值恰好就是算法中回代那两行。
终止性：每次递归第二参数从 b 变成 a mod b < b，严格递减的非负整数序列必然在有限步内到 0，所以算法必终止。∎
证明的关键点：① 归纳参数选"步数"而不是"数值大小"；② 必须用辗转相除恒等式把 gcd(b, a mod b) 换成 gcd(a, b)；③ 回代公式不是"猜"出来的，而是把 a mod b 展开后整理出来的。
易错：归纳假设里漏掉"gcd(b, a mod b) = gcd(a, b)"这一步，导致等号两边对不上；或者只证终止性不证正确性。
C3综合编程
【P1516 青蛙的约会】两只青蛙在长度为 L 的环形数轴上跳跃，起点 x、y，每步跳 m、n 米，同向起跳。求最少跳多少次能相遇，无解输出 Impossible。
查看参考答案
建模：(x + m·t) ≡ (y + n·t) (mod L) → (m − n)·t ≡ y − x (mod L)。
#include<bits/stdc++.h>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 g = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
return g;
}
int main() {
ll x, y, m, n, L; cin >> x >> y >> m >> n >> L;
ll a = m - n, c = y - x;
if (a < 0) { a = -a; c = -c; }
ll x0, y0;
ll g = exgcd(a, L, x0, y0);
if (c % g) { cout << "Impossible" << endl; return0; }
ll t = L / g;
ll ans = (ll)((__int128)((x0 % t + t) % t) * ((c / g) % t + t) % t);
if (ans == 0) ans = t;
cout << ans << endl;
return0;
}