裴蜀定理与扩展欧几里得算法详解

代码分析

• 时间复杂度：O(nlogM)，其中 M 是序列中元素的最大值。每次调用欧几里得算法的时间复杂度为 O(logM)，共调用 n-1 次。
• 关键优化：由于 gcd 的性质，当计算过程中 ret=1 时，后续元素的 gcd 不可能更小，可直接退出循环。
• 边界处理：序列元素可能为负，需取绝对值后再计算 gcd（gcd 的结果与输入正负无关）。

二、扩展欧几里得算法：不定方程的求解工具

裴蜀定理告诉我们方程 ax+by=c 何时有解，但没有给出具体的求解方法。而扩展欧几里得算法（Extended Euclidean Algorithm）正是裴蜀定理的延伸——它不仅能计算 a 和 b 的最大公约数，还能同时求出方程 ax+by=gcd(a,b) 的一组特解，进而推导出所有整数解。

2.1 算法的核心推导

扩展欧几里得算法的推导基于欧几里得算法（辗转相除法）的递归过程，我们通过逐步拆解来理解其逻辑：

步骤 1：欧几里得算法的递归性质

欧几里得算法的核心是 gcd(a,b)=gcd(b,a mod b)，当 b=0 时，gcd(a,0)=a。

步骤 2：递归终止条件

当 b=0 时，方程 ax+by=gcd(a,b) 简化为 ax=a，此时一组特解为 x=1，y=0（因为 a×1+0×0=a=gcd(a,0)）。

步骤 3：递归过程的解推导

假设我们已经求出了递归下一层的解：对于 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

通过这种方式，我们可以从递归终止条件反向推导，逐步求出原方程的一组特解。

2.2 算法的 C++ 实现（递归版）

#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;
}

2.3 算法的非递归实现（可选）

递归实现简洁直观，但对于极端数据（如 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;
}

2.4 通解的推导

扩展欧几里得算法求出的是方程 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，满足方程。

2.5 方程 ax+by=c 的求解流程

当方程 ax+by=c 有解（即 d∣c，d=gcd(a,b)）时，求解流程如下：

1. 用扩展欧几里得算法求出方程 ax+by=d 的一组特解 (x0,y0)。
2. 将特解缩放 k=c/d 倍，得到原方程的一组特解：x1=x0·k，y1=y0·k。
3. 原方程的通解为： x = x1 + k·(b/d) (k∈Z) y = y1 - k·(a/d) (k∈Z)

示例：求解 6x+8y=4

• 计算 d=gcd(6,8)=2，c=4，k=4/2=2。
• 求出 6x+8y=2 的特解 (x0=-1,y0=1)。
• 原方程特解：x1=-1×2=-2，y1=1×2=2（6×(-2)+8×2=-12+16=4，正确）。
• 通解：x=-2+4k，y=2-3k（k 为整数）。

三、实战例题 3：洛谷 P5656【模板】二元一次不定方程 (exgcd)

3.1 题目分析

题目描述：给定不定方程 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 或 y 为 0 的情况（0 不是正整数）。
• 避免数值溢出，需使用长整型。

3.2 解题思路

• 用扩展欧几里得算法判断方程是否有解（c%d==0），无解则输出 -1。
• 有解则求出特解，并推导通解。
• 计算 x 的最小正整数值，进而求出对应的 y，判断是否为正整数：若 y>0，则存在正整数解，计算解的个数和其他极值；若 y≤0，则无正整数解，输出 x 和 y 的最小正整数值。

关键公式推导

设通解为 x = x1 + k·(b/d), y = y1 - k·(a/d)：

• 代入 xmin 求出对应的 y，若 y>0，则 ymax=y。
• 代入 ymin 求出对应的 x，即为 xmax。
• 正整数解的个数：(xmax - xmin) / (b/d) + 1。
• y 的最小正整数值：(y1 % (a/d) + (a/d)) % (a/d)，若结果为 0 则取 a/d。
• x 的最小正整数值：(x1 % (b/d) + (b/d)) % (b/d)，若结果为 0 则取 b/d。

3.3 C++ 实现

#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 > 0) { // 存在正整数解
            minx = x;
            maxy = y;
            // 计算 y 的最小正整数值
            y = (y % k2 + k2) % k2;
            if (y == 0) y = k2;
            miny = y;
            // 计算 x 的最大正整数值
            maxx = (c - b * y) / a;
            // 计算解的个数
            LL cnt = (maxx - minx) / k1 + 1;
            printf("%lld %lld %lld %lld %lld\n", cnt, minx, miny, maxx, maxy);
        } else { // 无正整数解，输出 x 和 y 的最小正整数值
            minx = x;
            y = (y % k2 + k2) % k2;
            if (y == 0) y = k2;
            miny = y;
            printf("%lld %lld\n", minx, miny);
        }
    }
    return 0;
}

四、常见误区与避坑指南

4.1 数值溢出问题

• 误区：使用 int 类型存储大数值（如 a、b 达到 1e9），导致乘法或加法溢出。
• 避坑：所有变量统一使用 long long 类型，尤其是在计算 a×x、b×y 时，避免溢出。

4.2 特解缩放错误

• 误区：求解 ax+by=c 时，忘记将特解缩放 k=c/d 倍。
• 反例：方程 6x+8y=4，若直接使用 6x+8y=2 的特解 (-1,1)，会得到 6×(-1)+8×1=2≠4。
• 避坑：牢记'特解缩放'步骤，确保解满足目标方程。

4.3 最小正整数解计算错误

• 误区：将特解直接取模后未处理负数情况。
• 反例：特解 x=-1，b/d=4，直接取模得 -1%4=-1，并非最小正整数解。
• 避坑：使用公式 (x%k+k)%k（k=b/d），确保结果为正整数。

4.4 通解增量搞反

• 误区：混淆通解中 x 和 y 的增量/减量。
• 避坑：牢记通解公式：x 的增量为 b/d，y 的减量为 a/d，二者符号相反。

4.5 忽略方程转化时的符号

• 误区：将同余方程 ax ≡ b(mod m) 错误转化为 ax+my=b（正确应为 ax-my=b）。
• 避坑：严格按照同余定义进行转化，确保方程等价性。

总结

本文详细讲解了裴蜀定理与扩展欧几里得算法的理论基础及 C++ 实现，涵盖了从定理判定、特解求解到通解推导的全过程，并结合实战例题分析了常见误区与优化技巧。掌握这些内容有助于高效解决算法竞赛中的数论相关问题。