扩展欧几里得算法演示

递归展开过程 (欧几里得算法)

参数变化表格

层级	a	b	q = ⌊a/b⌋	r = a mod b	状态

回溯求解 Bézout 系数 (x, y)

最终解

计算完成！最大公约数 (gcd) 和一组 Bézout 系数 (x, y) 如下：

Bézout 恒等式的几何直观

Bézout 恒等式 ax + by = d 可以看作是两个向量 (a, 0) 和 (0, b) 的线性组合，通过整数系数 x 和 y 缩放并相加，最终可以构造出表示最大公约数 d 的某种形式（例如向量 (d, ...) 或表示长度为 d 的线段）。下图尝试展示这种关系。

Bézout 方程的通解形式

▼

扩展欧几里得算法找到的是方程 ax + by = d (其中 d = gcd(a, b)) 的一组特解 (x₀, y₀)。

该方程实际上有无穷多组整数解，其通解形式为：

x = x₀ + k * (b / d), y = y₀ - k * (a / d)

其中 k 可以是任意整数 (k ∈ ℤ)。

这表明所有整数解在二维平面上构成一系列等距分布的点，它们都落在直线 ax + by = d 上。

学习小贴士与应用场景

💡模乘法逆元

当我们需要求解 ax ≡ 1 (mod m) 中的 x 时（要求 gcd(a, m) = 1），这等价于求解线性丢番图方程 ax + my = 1。

使用扩展欧几里得算法计算 a 和 m，得到 ax' + my' = 1。此时得到的 x' 就是 a 模 m 的一个乘法逆元。最终结果可能需要调整到 [0, m-1] 范围内，即 x = (x' % m + m) % m。

⚠️常见误区

1. 回代公式混淆： 记住递归返回时，是基于下一层的解 (x₂, y₂) 来计算当前层的解 (x₁, y₁)，公式为 x₁ = y₂, y₁ = x₂ - ⌊a/b⌋ * y₂。

2. 符号处理： 回代过程中减法和负数系数要格外小心。

3. 基准情况： 递归基准是当 b = 0 时，gcd(a, 0) = a，此时 x = 1, y = 0，因为 a * 1 + 0 * 0 = a。

🔧线性丢番图方程

对于一般形式的方程 ax + by = c，它有整数解的充要条件是 gcd(a, b) 能够整除 c (即 c % gcd(a, b) == 0)。

如果满足条件，可以先用 ExGCD 求出 ax' + by' = d (其中 d = gcd(a, b)) 的一组解 (x', y')。然后，将整个方程两边同乘以 c / d，得到：a * (x' * c/d) + b * (y' * c/d) = d * (c/d) = c。因此，原方程的一组特解是 x = x' * (c/d), y = y' * (c/d)。

扩展欧几里得算法的 C++ 实现

递归实现 (Recursive)

// 函数功能：计算 a 和 b 的最大公约数 d，并找到一组整数 x, y 使得 ax + by = d
// 参数：a, b 为输入的非负整数
// 参数：x, y 为引用的整数变量，用于存储计算得到的 Bézout 系数
// 返回值：a 和 b 的最大公约数 d
long long exgcd_recursive(long long a, long long b, long long &x, long long &y) {
    // 递归基准情况：当 b = 0 时
    if (b == 0) {
        // gcd(a, 0) = a
        // 此时满足 a * 1 + 0 * 0 = a，所以 x = 1, y = 0
        x = 1;
        y = 0;
        return a;
    }

    // 递归调用：求解 gcd(b, a % b)
    // 我们需要找到 x₂ 和 y₂ 使得 b * x₂ + (a % b) * y₂ = gcd(b, a % b)
    long long x2, y2;
    long long d = exgcd_recursive(b, a % b, x2, y2); // d = gcd(a, b) = gcd(b, a % b)

    // 回代计算：根据 x₂, y₂ 推导 x, y
    // 已知: b * x₂ + (a % b) * y₂ = d
    // 因为 a % b = a - floor(a / b) * b
    // 代入得: b * x₂ + (a - (a / b) * b) * y₂ = d
    // 整理得: b * x₂ + a * y₂ - (a / b) * b * y₂ = d
    // 合并 b 的项: a * y₂ + b * (x₂ - (a / b) * y₂) = d
    // 对比 ax + by = d，可知当前层的解为:
    x = y2;
    y = x2 - (a / b) * y2; // 注意：这里的 (a / b) 是整数除法 floor(a/b)

    return d; // 返回最大公约数
}

迭代实现 (Iterative)

// 函数功能：迭代计算 a 和 b 的最大公约数 d，并找到一组整数 x, y 使得 ax + by = d
// 参数和返回值同递归版本
long long exgcd_iterative(long long a, long long b, long long &x, long long &y) {
    // 初始化：对应递归基准情况 gcd(a, 0) = a, x=1, y=0
    long long x0 = 1, y0 = 0; // 对应 a 的系数
    long long x1 = 0, y1 = 1; // 对应 b 的系数

    // 循环进行辗转相除，同时更新系数
    // 初始状态: a = a * x0 + b * y0; b = a * x1 + b * y1
    while (b != 0) {
        long long q = a / b; // 计算商
        long long temp;

        // 更新 a 和 b (辗转相除)
        temp = b;
        b = a % b;
        a = temp;

        // 更新 Bézout 系数
        // 新的 x0', y0' (对应新的 a，即原来的 b) 来源于原来的 x1, y1
        // 新的 x1', y1' (对应新的 b，即原来的 a % b) 通过关系推导
        // r = a - q*b  =>  a*x1 + b*y1 = (a_old*x0 + b_old*y0) - q * (a_old*x1 + b_old*y1)
        // 整理得: a_old * (x0 - q*x1) + b_old * (y0 - q*y1)
        // 所以新的系数是 (x0 - q*x1) 和 (y0 - q*y1)

        temp = x1;
        x1 = x0 - q * x1;
        x0 = temp;

        temp = y1;
        y1 = y0 - q * y1;
        y0 = temp;
    }

    // 循环结束时，a 是最大公约数 d
    // 此时的 x0, y0 满足 a_final * x0 + b_final(=0) * y0 = d
    x = x0;
    y = y0;
    return a; // 返回最大公约数 a
}

注意：使用 long long 类型可以处理更大的输入整数，防止溢出。