C++算法
裴蜀定理与扩展欧几里得算法详解
裴蜀定理判定线性不定方程 ax+by=c 有解的充要条件是 gcd(a,b) 整除 c。扩展欧几里得算法用于求解该方程的一组特解，进而推导通解。文章涵盖定理表述、推论、递归与非递归实现代码、通解公式推导及实战例题分析。重点讲解最小正整数解计算、数值溢出处理及常见误区避坑指南，适用于算法竞赛中的数论问题求解。
裴蜀定理判定线性不定方程 ax+by=c 有解的充要条件是 gcd(a,b) 整除 c。扩展欧几里得算法用于求解该方程的一组特解，进而推导通解。文章涵盖定理表述、推论、递归与非递归实现代码、通解公式推导及实战例题分析。重点讲解最小正整数解计算、数值溢出处理及常见误区避坑指南，适用于算法竞赛中的数论问题求解。
在算法竞赛的数论版图中，裴蜀定理和扩展欧几里得算法是解决线性不定方程、同余方程、乘法逆元等核心问题的底层支撑。它们不仅是判定方程是否有解的工具，还能精准求出解的具体形式，更是后续学习中国剩余定理、模运算优化等高级内容的基础。
裴蜀定理（又称贝祖定理）是数论中关于线性不定方程的基础定理，其核心表述为：
对于任意整数 a、b，一定存在整数 x、y，使得 ax+by=gcd(a,b)。
其中 gcd(a,b) 表示 a 和 b 的最大公约数。这个定理揭示了线性不定方程有解的本质条件 —— 方程 ax+by=c 有整数解的充要条件是 gcd(a,b)∣c（即 c 能被 a 和 b 的最大公约数整除）。
取 a=6，b=8：gcd(6,8)=2，根据裴蜀定理，存在整数 x、y 使得 6x+8y=2。例如 x=-1，y=1（6×(-1)+8×1=2）；取 a=5，b=7：gcd(5,7)=1，存在整数 x=3，y=-2 使得 5×3+7×(-2)=1；反例：方程 6x+8y=3 无解，因为 gcd(6,8)=2 不能整除 3。
裴蜀定理可以推广到多个整数的情况，其核心推论有两个，是解决复杂问题的关键：
以二元推广为例，当我们遇到方程 ax+by=c 时，无需盲目求解，先计算 gcd(a,b) 并判断是否能整除 c：若不能整除，直接判定无解；若能整除，再进一步求解，可大幅节省时间。
题目描述：给定包含 n 个元素的整数序列 A，求另一个整数序列 X，使得 ∑Ai×Xi 且 S 尽可能小。
输入描述：第一行一个整数 n，第二行 n 个整数表示序列 A。
输出描述：一行一个整数，表示满足条件的最小 S。
示例输入：2 4059 -1782 → 输出：99。
核心思路：根据裴蜀定理的多元推广，∑Ai×Xi 的所有可能结果都是 gcd(A1,A2,...,An) 的倍数。因此，最小的正结果就是所有元素的最大公约数的绝对值（因为序列中可能有负数，gcd 本身非负）。
#include <iostream>
#include <cmath>
using namespace std;
// 欧几里得算法求 gcd
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int ret;
cin >> ret;
ret = abs(ret); // 取绝对值，避免负数影响 gcd 计算
for (int i = 2; i <= n; ++i) {
int x;
cin >> x;
ret = gcd(ret, abs(x)); // 依次计算所有元素的 gcd
if (ret == 1) break; // gcd 最小为 1，可提前退出
}
cout << ret << endl;
return 0;
}
裴蜀定理告诉我们方程 ax+by=c 何时有解，但没有给出具体的求解方法。而扩展欧几里得算法（Extended Euclidean Algorithm）正是裴蜀定理的延伸——它不仅能计算 a 和 b 的最大公约数，还能同时求出方程 ax+by=gcd(a,b) 的一组特解，进而推导出所有整数解。
扩展欧几里得算法的推导基于欧几里得算法（辗转相除法）的递归过程，我们通过逐步拆解来理解其逻辑：
欧几里得算法的核心是 gcd(a,b)=gcd(b,a mod b)，当 b=0 时，gcd(a,0)=a。
当 b=0 时，方程 ax+by=gcd(a,b) 简化为 ax=a，此时一组特解为 x=1，y=0（因为 a×1+0×0=a=gcd(a,0)）。
假设我们已经求出了递归下一层的解：对于 gcd(b,a mod b)，存在整数 x1、y1 使得 bx1+(a mod b)y1=gcd(b,a mod b)。
由于 a mod b = a - (a/b)*b，代入上式得：
bx1 + (a - (a/b)*b)y1 = gcd(a,b)
整理后：
ay1 + b(x1 - (a/b)y1) = gcd(a,b)
对比目标方程 ax+by=gcd(a,b)，可得当前层的解为：
x = y1 y = x1 - (a/b)*y1
通过这种方式，我们可以从递归终止条件反向推导，逐步求出原方程的一组特解。
#include <iostream>
using namespace std;
typedef long long LL;
// 扩展欧几里得算法：返回 gcd(a,b)，并通过引用返回方程 ax+by=gcd(a,b) 的一组特解 (x,y)
LL exgcd(LL a, LL b, LL& x, LL& y) {
if (b == 0) { // 递归终止条件：b=0 时，x=1，y=0
x = 1;
y = 0;
return a;
}
// 递归计算下一层
LL x1, y1, d;
d = exgcd(b, a % b, x1, y1);
// 推导当前层的解
x = y1;
y = x1 - (a / b) * y1;
return d;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
LL a = 6, b = 8;
LL x, y;
LL d = exgcd(a, b, x, y);
cout << "gcd(" << a << ", " << b << ") = " << d << endl;
cout << "方程 " << a << "x + " << b << "y = " << d << " 的一组特解：x = " << x << ", y = " << y << endl;
// 输出：gcd(6,8)=2；特解 x=-1, y=1（6*(-1)+8*1=2）
return 0;
}
递归实现简洁直观，但对于极端数据（如 a、b 达到 1e18）可能导致栈溢出。以下是非递归版本的实现，逻辑与递归版一致：
#include <iostream>
using namespace std;
typedef long long LL;
LL exgcd_non_recursive(LL a, LL b, LL& x, LL& y) {
LL x0 = 1, y0 = 0; // 初始状态：b=0 时的解
LL x1 = 0, y1 = 1; // 初始状态：a=b, b=a%b 时的解
x = 0, y = 1;
LL d = a;
while (b != 0) {
LL q = a / b; // 商
LL r = a % b; // 余数
// 更新 a 和 b
a = b;
b = r;
// 更新解
LL tx = x;
LL ty = y;
x = x0 - q * x1;
y = y0 - q * y1;
x0 = x1;
y0 = y1;
x1 = tx;
y1 = ty;
}
x = x0;
y = y0;
return a;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
LL a = 6, b = 8;
LL x, y;
LL d = exgcd_non_recursive(a, b, x, y);
cout << "gcd(" << a << ", " << b << ") = " << d << endl;
cout << "特解：x = " << x << ", y = " << y << endl;
return 0;
}
扩展欧几里得算法求出的是方程 ax+by=gcd(a,b) 的一组特解 (x0,y0)，但方程的解有无穷多个。我们可以通过特解推导出所有整数解（通解）：
设 d=gcd(a,b)，令 a'=a/d，b'=b/d（此时 a' 和 b' 互质）。对于方程 ax+by=d，其通解为： x = x0 + k·b' (k∈Z) y = y0 - k·a' (k∈Z)
由于 a'x0+b'y0=1（两边除以 d 得到），代入通解： a(x0+k·b') + b(y0-k·a') = ax0 + ab'k + by0 - ba'k
由于 ab'-ba'=0，因此 ax0+by0=d，满足方程。
当方程 ax+by=c 有解（即 d∣c，d=gcd(a,b)）时，求解流程如下：
题目描述：给定不定方程 ax+by=c，判断是否有整数解。若无解，输出 -1；若有解但无正整数解（x>0，y>0），输出 x 和 y 的最小正整数值；若有正整数解，输出正整数解的个数、x 的最小值、y 的最小值、x 的最大值、y 的最大值。
输入描述：第一行一个整数 T，每组数据一行三个正整数 a、b、c。
输出描述：按题目要求输出对应结果。
示例输入：7 2 11 100 → 输出：4 6 2 39 8。
核心难点：
设通解为 x = x1 + k·(b/d), y = y1 - k·(a/d)：
#include <iostream>
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 x1, y1, d;
d = exgcd(b, a % b, x1, y1);
x = y1, y = x1 - a / b * y1;
return d;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
scanf("%d", &T);
while (T--) {
LL a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
LL x, y, d;
d = exgcd(a, b, x, y);
if (c % d != 0) { // 无解
printf("-1\n");
continue;
}
// 求出原方程的一组特解
LL k = c / d;
x = x * k, y = y * k;
LL k1 = b / d; // x 的增量
LL k2 = a / d; // y 的减量
// 计算 x 的最小正整数值
x = (x % k1 + k1) % k1;
if (x == 0) x = k1;
// 对应的 y 值
y = (c - a * x) / b;
LL minx, miny, maxx, maxy;
if (y > ) {
minx = x;
maxy = y;
y = (y % k2 + k2) % k2;
(y == ) y = k2;
miny = y;
maxx = (c - b * y) / a;
LL cnt = (maxx - minx) / k1 + ;
(, cnt, minx, miny, maxx, maxy);
} {
minx = x;
y = (y % k2 + k2) % k2;
(y == ) y = k2;
miny = y;
(, minx, miny);
}
}
;
}
本文详细讲解了裴蜀定理与扩展欧几里得算法的理论基础及 C++ 实现，涵盖了从定理判定、特解求解到通解推导的全过程，并结合实战例题分析了常见误区与优化技巧。掌握这些内容有助于高效解决算法竞赛中的数论相关问题。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online