扩展欧几里得算法（Exgcd）

扩展欧几里得算法：从“凑出最大公约数”到解方程的秘密

你已经知道欧几里得算法（辗转相除法）能快速求出两个数的最大公约数（gcd）。但很多时候我们不仅仅只想知道 gcd，还想知道“怎么用这两个数凑出这个 gcd”。比如：你有 a 颗糖和 b 颗糖，你想分给小朋友们，每个小朋友要拿到同样多的糖，并且每个小朋友拿到的糖数正好是 a 和 b 的最大公约数。那么你需要从第一堆里拿 x 份，从第二堆里拿 y 份，使得 a * x + b * y = gcd(a, b)。这个方程的解 x、y 就是“扩展欧几里得算法”要找的。

更一般地说，扩展欧几里得算法能求解形如 a * x + b * y = c 的方程（线性不定方程）的整数解，只要 c 是 gcd(a,b) 的倍数。它也是后续学习模逆元、中国剩余定理、解同余方程的重要基础。

生活中的比喻：跳格子与拼零花钱

想象你和朋友在玩跳格子游戏。你一次可以跳 a 格，朋友一次可以跳 b 格。你们想跳到同一个格子，并且这个格子离起点越近越好（其实就是 gcd 步）。那么你们各自要跳几次（x 和 y 可能是负数，表示往回跳）才能正好踩到那个格子上？扩展欧几里得算法就能算出来。

再举个零花钱的例子：你每周有 a 元零花钱，朋友有 b 元，你们想凑出正好等于 gcd(a,b) 元去给妈妈买一束小花。你们可以互相借钱（负数表示借给别人），怎样才能刚好凑出这笔钱？扩展欧几里得算法会告诉你每人该出多少钱（即 x 和 y）。

算法思路：递归的奇妙递推

我们用递归来求解 a * x + b * y = gcd(a, b)。核心思想是：如果知道了 b 和 a % b 的解，就能反推出 a 和 b 的解。

递归基（最简单的情况）

当 b == 0 时，gcd = a，方程变成 a * x + 0 * y = a，显然 x = 1, y = 0 是一组解。这是递归的出口。

递归步骤

假设我们已经知道了 b * x2 + (a % b) * y2 = gcd(b, a % b) 的一组解 (x2, y2)。注意 a % b 其实就是 a - (a / b) * b（其中 / 是整除）。我们想要找到 a * x + b * y = gcd(a, b) 的解。因为 gcd(a,b) = gcd(b, a%b)，所以目标式子的右侧等于左侧式子的右侧。

从已知式子出发：

b * x2 + (a - (a/b) * b) * y2 = gcd

展开并合并 b 的系数：

b * x2 + a * y2 - (a/b) * b * y2 = a * y2 + b * (x2 - (a/b) * y2)

对比目标式 a * x + b * y = gcd，我们可以取：

x = y2
y = x2 - (a / b) * y2

这样就由 (x2, y2) 推出了 (x, y)。

推导总结（可以记成公式）

x = y2
y = x2 - (a / b) * y2

其中 (x2, y2) 是递归下一层的解。a / b 是整数除法（C++ 中自动向下取整）。

逐步计算示例（以 a=15, b=6 为例）

我们手动走一遍递归过程，看看 x,y 是怎么变出来的：

1. exgcd(15, 6)

   • a=15, b=6, 计算下一层：exgcd(6, 15%6=3)

2. exgcd(6, 3)

   • a=6, b=3, 下一层：exgcd(3, 6%3=0)

3. exgcd(3, 0)

   • b==0，返回 x2=1, y2=0, gcd=3
   • 回到上一层：x = y2 = 0, y = x2 - (6/3)y2 = 1 - 20 = 1
   • 得到一对解 (x=0, y=1) 对于方程 6x + 3y = 3

4. 回到 exgcd(6, 3) 的上一层（即 exgcd(15,6)）

   • 上一层的 x2 = 0, y2 = 1
   • x = y2 = 1
   • y = x2 - (15/6)y2 = 0 - 21 = -2
   • 得到 (x=1, y=-2) 对于 15x + 6y = 3

验证：15×1 + 6×(-2) = 15 - 12 = 3。✅

新手容易犯的错误

1. 递归结束条件写错：有些同学写成 if (b == 1) 或 if (a == 0)，导致无限递归或错误结果。一定要是 b == 0。
2. 引用传递忘记写 &：int exgcd(int a, int b, int &x, int &y) 中 x 和 y 必须是引用，否则修改传不回去，函数里求出的解带不到外面。
3. 混淆 x 和 y 的赋值顺序：公式是 x = y2; y = x2 - (a/b)*y2;，不要写成 x = x2; y = y2。
4. 认为 x 和 y 一定非负：从例子可以看到，x 和 y 常常一正一负，这是正常的。负号表示“向相反方向走”（比如借钱）。
5. 忘记返回值：函数需要返回 gcd，不要只求了 x,y 忘记 return。

C++ 完整代码（带输入、输出与验证）

下面是一个可以自己输入 a 和 b 的完整程序，并会输出多组解（实际上扩展欧几里得只返回一组特殊解，但你可以通过加减 b/gcd 得到其他解）。

#include <iostream>
using namespace std;

// 扩展欧几里得：返回 gcd(a,b)，同时通过引用传出 x,y 满足 a*x + b*y = gcd
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x2, y2;               // 递归求出的下层解
    int g = exgcd(b, a % b, x2, y2);
    x = y2;
    y = x2 - (a / b) * y2;
    return g;
}

int main() {
    int a, b;                 // 输入的两个数
    cout << "请输入两个正整数 a 和 b（用空格隔开）: ";
    cin >> a >> b;

    int x, y;                 // 用来接收解
    int g = exgcd(a, b, x, y);

    cout << "gcd(" << a << ", " << b << ") = " << g << endl;
    cout << "一组整数解为: x = " << x << ", y = " << y << endl;
    cout << "验证: " << a << " * " << x << " + " << b << " * " << y
         << " = " << a * x + b * y << endl;

    // 扩展：展示通解（可选）
    // 通解：x' = x + t * (b/g), y' = y - t * (a/g)
    cout << "\n通解公式：" << endl;
    cout << "x' = " << x << " + t * (" << b / g << ")" << endl;
    cout << "y' = " << y << " - t * (" << a / g << ")" << endl;
    cout << "例如 t=1 时：x'=" << x + (b / g) << ", y'=" << y - (a / g) << endl;

    return 0;
}

运行示例（输入 100 45）：

请输入两个正整数 a 和 b（用空格隔开）: 100 45
gcd(100, 45) = 5
一组整数解为: x = -5, y = 11
验证: 100 * (-5) + 45 * 11 = -500 + 495 = -5?  等等不对？！

咦？这里我们发现结果验证不对？别急！仔细看 100 * (-5) + 45 * 11 = -500 + 495 = -5，但 gcd 是 5，不是 -5。这是因为我们算法返回的 x,y 满足 a*x + b*y = gcd 的 绝对值 正确，但符号可能因递归顺序导致 gcd 为负数？实际上我们的算法正确时 gcd 总是正数，但这里出现了 -5，说明代码有细节错误。

检查：我们递归时 exgcd(b, a % b, x2, y2) 返回的是正 gcd，但 a % b 在 C++ 中对于正数为正，所以一切正常。为什么会得到 -5？让我们手工验证：100*(-5)+45*11 = -500+495 = -5。而 gcd(100,45)=5。显然解应该是 100*x + 45*y = 5，而不是 -5。说明我们求出的 x,y 实际上满足的是 a*x + b*y = -gcd？通常标准模板得到的解满足 |a*x + b*y| = gcd，但符号可能不对？实际上是 x=-5, y=11 这组解满足 100*(-5) + 45*11 = -5，但乘以 -1 后得到 100*5 + 45*(-11) = 5，所以 x=5, y=-11 也是一组解。扩展欧几里得算法通常保证 |x| <= |b|/gcd 左右，但不保证符号。这里得到的解是负的，你可以通过取反或加上通解来得到正的方程右边。

但是标准扩展欧几里得算法确实应该返回满足 正 gcd 的 x,y。我们检查一下代码：exgcd(100,45) 递归过程：

• exgcd(100,45): a=100, b=45, 递归 exgcd(45, 100%45=10)
• exgcd(45,10): a=45, b=10, 递归 exgcd(10, 45%10=5)
• exgcd(10,5): a=10, b=5, 递归 exgcd(5, 0)
• exgcd(5,0): 返回 x=1,y=0,g=5
• 回 exgcd(10,5): x2=1,y2=0; x = y2 = 0; y = x2 - (10/5)y2 = 1 - 20 = 1; 返回 (0,1) 和 g=5 => 100 + 51 = 5 正确
• 回 exgcd(45,10): x2=0,y2=1; x = y2 = 1; y = x2 - (45/10)y2 = 0 - 41 = -4; 返回 (1,-4) 和 g=5 => 451 + 10(-4) = 45-40=5 正确
• 回 exgcd(100,45): x2=1,y2=-4; x = y2 = -4; y = x2 - (100/45)y2 = 1 - 2(-4) = 1 + 8 = 9; 返回 (-4,9) 和 g=5 => 100*(-4) + 45*9 = -400 + 405 = 5 ✅

咦？手工计算得到 x=-4, y=9，而程序输出 x=-5, y=11？哪里出错了？原来我在上面写示例运行时用的是“100 45”，但代码中 a / b 是整数除法，100/45 = 2（因为 45*2=90，余10），正确。递归过程中没有错误，为什么程序会输出不同？哦，我上面示例运行时我脑补了错误数字。实际上正确输出应该是 x=-4,y=9。让我们修正示例：运行结果应该是：

请输入两个正整数 a 和 b（用空格隔开）: 100 45
gcd(100, 45) = 5
一组整数解为: x = -4, y = 9
验证: 100 * (-4) + 45 * 9 = -400 + 405 = 5

好，这才是正确的。所以新手要小心：不要在写文章时编造错误的输出，要实际运行验证。我们后续保留正确输出。

常见错误二：误解通解公式

扩展欧几里得只求出 一组 特解 (x0, y0)。所有整数解可以表示为：

x = x0 + t * (b / g)
y = y0 - t * (a / g)

其中 g = gcd(a, b)，t 为任意整数。比如上面例子，x0 = -4, y0 = 9, g=5，通解为：

x = -4 + t * (45/5) = -4 + 9t
y = 9  - t * (100/5) = 9 - 20t

t=1 时得到 x=5, y=-11，验证：1005 + 45(-11) = 500 - 495 = 5 ✅

很多新手只记得特解，却不知道如何得到其他解，导致在解方程 a*x + b*y = c（c不一定等于gcd）时出错。

如何解更一般的方程：ax + by = c

如果 c 不是 gcd(a,b) 的倍数，则方程无整数解。如果是倍数，设 g = gcd(a,b)，先求出 a*x0 + b*y0 = g 的一组解，然后乘以 c/g：

x = x0 * (c / g)
y = y0 * (c / g)

这样得到的就是原方程的一组特解。

例子：解 100*x + 45*y = 10。已知 g=5，c/g=2，所以特解为 x = -42 = -8, y = 92 = 18。验证：100*(-8)+45*18 = -800 + 810 = 10 ✅。

总结与相关知识点

扩展欧几里得算法的核心在于通过递归将问题规模缩小，利用 gcd(a,b) = gcd(b, a%b) 的性质，并找到两组解之间的关系。它的主要应用有：

• 求解线性不定方程：a*x + b*y = c 的整数解。
• 求乘法逆元：求 a 关于模 m 的逆元，即解 a*x ≡ 1 (mod m)，等价于解 a*x + m*y = 1（当 gcd(a,m)=1 时）。
• 中国剩余定理：需要解多个同余方程，会反复用到扩展欧几里得。

掌握了扩展欧几里得，你就打开了一扇通向数论算法的大门。下一步可以学习：

• [乘法逆元（模逆元）与费马小定理]
• [线性同余方程与同余方程组]
• [中国剩余定理]

动手试试：把上面的代码改成输出通解，然后输入你喜欢的数字，比如 (17, 13)，看看能不能算出 x,y 使得 17x+13y=1（因为 gcd=1，这就是求 17 模 13 的逆元）。