扩展欧几里得算法：不仅能求最大公约数，还能解出“怎么凑”

你有没有想过这样的问题：假如你手里只有两种面值的硬币，比如1元和5元，想凑出13元，该怎么组合？设1元硬币用 $x$ 个，5元硬币用 $y$ 个，那问题就变成了解方程 $1x + 5y = 13$。这个方程在数学上叫二元一次不定方程，它有没有整数解？有的话怎么找到？扩展欧几里得算法就是解决这类问题的最核心工具。

扩展欧几里得算法（Extended Euclidean Algorithm，简称 Exgcd）是从普通欧几里得算法（也就是辗转相除法）升级而来的。普通欧几里得算法只能算出两个数的最大公约数（gcd），而扩展欧几里得算法不仅能算出 gcd，还能找到两个整数系数 $x$ 和 $y$，使得：

这里 $a$ 和 $b$ 是给定的非负整数（至少一个不为0）。这看起来像是一个“拆解”过程：把最大公约数用 $a$ 和 $b$ 的倍数加减表示出来。比如 $a=6, b=10$，$\gcd(6,10)=2$，你能找到 $6x+10y=2$ 的解吗？可以：$6\times 2 + 10\times(-1) = 12 - 10 = 2$，所以一组解是 $x=2, y=-1$。扩展欧几里得算法就能自动帮我们算出这样的 $x$ 和 $y$。

接下来我们一步步拆开这个算法。

1. 生活中的例子：用两种面值的硬币凑出最大公约数

假设你有两种面值的硬币：面值 $a$ 和 $b$（比如6元和10元）。你想凑出总金额恰好等于它们的最大公约数 $g$。扩展欧几里得算法告诉你：一定能找到整数个的硬币组合（允许“负个数”，理解为欠钱或找零）使得总金额等于 $g$。

比如 $a=6, b=10$，$\gcd=2$。你可以用两个6元硬币（12元）减去一个10元硬币（10元），相当于 $6\times 2 + 10\times(-1)=2$。这里 $x=2, y=-1$，说明你付出2个6元硬币，收回1个10元硬币，净付出2元。

再比如 $a=5, b=7$，$\gcd=1$。你能用5元和7元硬币凑出1元吗？可以：$5\times 3 + 7\times(-2)=15-14=1$，即3个5元减去2个7元。扩展欧几里得算法就能求出这样的 $x$ 和 $y$。

这种“凑数”的能力在现实中有很多应用：比如在计算机中计算模逆元（后面会提到），或者在解不定方程时找到一组特解。

2. 数学原理与递推公式

2.1 我们要解决的问题

给定非负整数 $a$ 和 $b$（至少一个不为0），求整数 $x$ 和 $y$ 使得：

同时我们也要算出 $\gcd(a,b)$ 本身。

2.2 从普通欧几里得开始

普通欧几里得算法不断做带余除法：

最后一步余数为0时，前一个余数就是 $\gcd(a,b)$。

现在扩展欧几里得在递归过程中，不仅返回 gcd，还返回一组系数 $(x,y)$ 使得当前两个数（比如 $a$ 和 $b$）满足线性组合等于 gcd。假设我们写一个递归函数 exgcd(a, b)，它返回一个三元组 $(g, x, y)$ 满足 $a\cdot x + b\cdot y = g$。

递归基：当 $b = 0$ 时，显然 $\gcd(a,0) = a$，而 $a\cdot 1 + 0\cdot 0 = a$，所以取 $x=1, y=0$。

递推步骤：当 $b \neq 0$ 时，我们先递归调用 exgcd(b, a % b)，得到一组系数 $(g, x_1, y_1)$ 满足：

注意 $a \bmod b = a - \lfloor a / b \rfloor \cdot b$，代入上式：

整理：

对比我们希望得到的式子 $a\cdot x + b\cdot y = g$，我们可以令：

这样就得到了当前层的系数。

这个公式可以这样记忆：递归返回的系数中，新的 $x$ 是旧的 $y_1$，新的 $y$ 是旧的 $x_1$ 减去商乘以旧的 $y_1$。

2.3 一步一步举例：求 gcd(6,10) 及系数

我们用表格展示递归过程。注意递归时参数顺序是 (a, b)，但实际调用中不要求 a ≥ b，算法照样工作（只是除法时注意 $\lfloor a/b \rfloor$ 对正数没问题）。

现在逐层向上回溯：

• 第5层 (a=2, b=0): 返回 (g=2, x1=1, y1=0)，因为 $2\cdot 1 + 0\cdot 0 = 2$。
• 第4层 (a=4, b=2): 接收下层返回的 (2, x1=1, y1=0)。计算 $\lfloor 4/2 \rfloor = 2$。
  新 $x = y1 = 0$，新 $y = x1 - 2\cdot y1 = 1 - 2\cdot 0 = 1$。
  得到 (2, 0, 1)，即 $4\cdot 0 + 2\cdot 1 = 2$。
• 第3层 (a=6, b=4): 接收下层 (2, x1=0, y1=1)。$\lfloor 6/4 \rfloor = 1$。
  新 $x = y1 = 1$，新 $y = x1 - 1\cdot y1 = 0 - 1 = -1$。
  得到 (2, 1, -1)$，即 $6\cdot 1 + 4\cdot(-1)=2$。
• 第2层 (a=10, b=6): 接收下层 (2, x1=1, y1=-1)。$\lfloor 10/6 \rfloor = 1$。
  新 $x = y1 = -1$，新 $y = x1 - 1\cdot y1 = 1 - 1\cdot(-1) = 2$。
  得到 (2, -1, 2)$，即 $10\cdot(-1) + 6\cdot 2 = -10+12=2$。
• 第1层 (a=6, b=10): 接收下层 (2, x1=-1, y1=2)。$\lfloor 6/10 \rfloor = 0$。
  新 $x = y1 = 2$，新 $y = x1 - 0\cdot y1 = -1$。
  最终得到 (2, 2, -1)$，即 $6\cdot 2 + 10\cdot(-1) = 12 - 10 = 2$。

所以 $\gcd(6,10)=2$，一组特解是 $x=2, y=-1$。

3. 通解与更多例子

上面得到的只是一组特解。实际上，如果 $x_0, y_0$ 是一组解，那么所有整数解可以写成：

其中 $g = \gcd(a,b)$。

例如对于 $6x+10y=2$，$g=2$，$\frac{b}{g}=5$，$\frac{a}{g}=3$，特解 $x_0=2, y_0=-1$，通解为：

当 $t=0$ 时就是 (2, -1)；$t=1$ 时得到 (7, -4)，验证：$6\times 7 + 10\times(-4)=42-40=2$，正确。

生活应用：如果你有6元和10元硬币，除了凑2元，还能凑出所有2的倍数（因为最大公约数是2）。通解告诉你，只要找到一组凑法，其他组合就是整体平移。

4. 新手容易犯的错误

1. 递归参数顺序搞反：有些同学在递归调用时写成 exgcd(a % b, b) 而不是 exgcd(b, a % b)。注意欧几里得算法是 gcd(a,b) = gcd(b, a%b)，所以递归时第一个参数是 b，第二个是 a % b，顺序不能错。

2. 忘记用临时变量保存 x1, y1：在递归返回后，必须先保存 x1 和 y1，然后再计算当前层的 x 和 y。如果直接用当前层的 x 和 y 去接收递归结果，会导致公式计算混乱（因为 x 的值被覆盖了）。

3. 整数除法取整问题：在 C++ 中 a / b 对于正数是向下取整，正好是公式所需的 $\lfloor a/b \rfloor$。但如果 a 或 b 出现负数，结果可能不同（向下取整 vs 向零取整）。扩展欧几里得通常只处理非负整数，如果遇到负数，可以先取绝对值或者用其他处理方式，初学者建议先只处理正数。

4. 返回值理解错误：有些同学以为返回的 x, y 是唯一的，实际上只是一组特解。要得到所有解，需要使用通解公式。

5. 对递归深度没有概念：递归的深度不超过 $O(\log \min(a,b))$，一般不用担心栈溢出，但如果是竞赛中数据极大（比如 $10^{18}$），深度也只有几十层，安全。

5. 完整代码示例（含详细中文注释）

C++ 实现

#include <iostream>
using namespace std;

// 扩展欧几里得：返回 gcd，并通过引用返回一组系数 x 和 y
// 要求：a, b 为非负整数，且至少一个不为 0
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {                // 递归基：gcd(a,0)=a
        x = 1;                   // a*1 + 0*0 = a
        y = 0;
        return a;
    }
    int x1, y1;                  // 临时变量，保存递归返回的系数
    int g = exgcd(b, a % b, x1, y1);  // 递归：b*x1 + (a%b)*y1 = g
    // 根据推导公式更新当前层的系数
    x = y1;                      // x 等于递归中的 y1
    y = x1 - (a / b) * y1;       // y 等于 x1 - floor(a/b)*y1
    return g;
}

int main() {
    // 测试一：6 和 10
    int a = 6, b = 10;
    int x, y;                    // 用于接收系数
    int g = exgcd(a, b, x, y);
    cout << "a=" << a << ", b=" << b << endl;
    cout << "gcd = " << g << endl;
    cout << "一组解：x = " << x << ", y = " << y << endl;
    cout << "验证：" << a << "*" << x << " + " << b << "*" << y << " = " << a*x + b*y << endl;
    cout << endl;

    // 测试二：48 和 18
    a = 48; b = 18;
    g = exgcd(a, b, x, y);
    cout << "a=" << a << ", b=" << b << endl;
    cout << "gcd = " << g << endl;
    cout << "一组解：x = " << x << ", y = " << y << endl;
    cout << "验证：" << a << "*" << x << " + " << b << "*" << y << " = " << a*x + b*y << endl;

    return 0;
}

Python 实现

def exgcd(a: int, b: int):
    """
    扩展欧几里得算法
    返回三元组 (g, x, y) 满足 a*x + b*y = g，其中 g = gcd(a, b)
    """
    if b == 0:
        return a, 1, 0  # gcd(a,0)=a, a*1+0*0=a
    g, x1, y1 = exgcd(b, a % b)  # 递归：b*x1 + (a%b)*y1 = g
    # 根据公式计算当前层的系数
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

# 测试一
a, b = 6, 10
g, x, y = exgcd(a, b)
print(f"a={a}, b={b}")
print(f"gcd = {g}")
print(f"一组解：x = {x}, y = {y}")
print(f"验证：{a}*{x} + {b}*{y} = {a*x + b*y}")
print()

# 测试二
a, b = 48, 18
g, x, y = exgcd(a, b)
print(f"a={a}, b={b}")
print(f"gcd = {g}")
print(f"一组解：x = {x}, y = {y}")
print(f"验证：{a}*{x} + {b}*{y} = {a*x + b*y}")

两个版本运行结果一致。注意 Python 中的 a // b 是整数除法（向下取整），对于正数与 C++ 的 / 相同。

6. 相关指引：学了 Exgcd 之后可以学什么？

扩展欧几里得算法是数论里的螺丝刀，它拧开了好几扇门：

• 求模逆元：在模 $m$ 下，想找一个数 $a^{-1}$ 使得 $a \cdot a^{-1} \equiv 1 \pmod{m}$，相当于解 $a x + m y = 1$，当 $\gcd(a,m)=1$ 时，Exgcd 给出的 $x$ 就是逆元。这在 RSA 加密和组合数学中非常常用。
• 解二元一次不定方程：对于方程 $ax + by = c$，如果 $\gcd(a,b) \mid c$，可以用 Exgcd 先解出 $ax+by=g$ 的一组特解，然后乘以 $c/g$ 得到原方程的特解，再写出通解。
• 求解同余方程组（中国剩余定理的基础）：需要求一组数的逆元，Exgcd 是核心工具。
• 算法竞赛：在信息学竞赛中，Exgcd 是必会算法，常出现在数学题和密码学题目中。

如果掌握了 Exgcd，下一步可以学习 裴蜀定理（即 $ax+by$ 能取到的所有整数就是 $g$ 的倍数），以及 最小正整数解 的求法。推荐动手画一画递归树，更直观地理解系数是如何“传递”的。