困难通用17 分钟6,119 字

扩展欧几里得算法(Exgcd)

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

扩展欧几里得算法(Extended Euclidean Algorithm,简称 Exgcd)是从普通欧几里得算法(也就是辗转相除法)升级而来的。普通欧几里得算法只能算出两个数的最大公约数(gcd),而扩展欧几里得算法不仅能算出 gcd,还能找到两个整数系数 xxx 和 yyy,使得:

a⋅x+b⋅y=gcd⁡(a,b)a \cdot x + b \cdot y = \gcd(a, b)a⋅x+b⋅y=gcd(a,b)

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

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


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

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

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

再比如 a=5,b=7a=5, b=7a=5,b=7,gcd⁡=1\gcd=1gcd=1。你能用5元和7元硬币凑出1元吗?可以:5×3+7×(−2)=15−14=15\times 3 + 7\times(-2)=15-14=15×3+7×(−2)=15−14=1,即3个5元减去2个7元。扩展欧几里得算法就能求出这样的 xxx 和 yyy。

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


2. 数学原理与递推公式

2.1 我们要解决的问题

给定非负整数 aaa 和 bbb(至少一个不为0),求整数 xxx 和 yyy 使得:

a⋅x+b⋅y=gcd⁡(a,b)a \cdot x + b \cdot y = \gcd(a, b)a⋅x+b⋅y=gcd(a,b)

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

2.2 从普通欧几里得开始

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

a=q1⋅b+r1(0≤r1<b)a = q_1 \cdot b + r_1 \quad (0 \le r_1 < b)a=q1​⋅b+r1​(0≤r1​<b)

b=q2⋅r1+r2b = q_2 \cdot r_1 + r_2b=q2​⋅r1​+r2​

⋯\cdots⋯

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

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

递归基​​:当 b=0b = 0b=0 时,显然 gcd⁡(a,0)=a\gcd(a,0) = agcd(a,0)=a,而 a⋅1+0⋅0=aa\cdot 1 + 0\cdot 0 = aa⋅1+0⋅0=a,所以取 x=1,y=0x=1, y=0x=1,y=0。

递推步骤​​:当 b≠0b \neq 0b=0 时,我们先递归调用 exgcd(b, a % b),得到一组系数 (g,x1,y1)(g, x_1, y_1)(g,x1​,y1​) 满足:

b⋅x1+(a mod b)⋅y1=gb \cdot x_1 + (a \bmod b) \cdot y_1 = gb⋅x1​+(amodb)⋅y1​=g

注意 a mod b=a−⌊a/b⌋⋅ba \bmod b = a - \lfloor a / b \rfloor \cdot bamodb=a−⌊a/b⌋⋅b,代入上式:

b⋅x1+(a−⌊a/b⌋⋅b)⋅y1=gb \cdot x_1 + (a - \lfloor a/b \rfloor \cdot b) \cdot y_1 = gb⋅x1​+(a−⌊a/b⌋⋅b)⋅y1​=g

整理:

a⋅y1+b⋅(x1−⌊a/b⌋⋅y1)=ga \cdot y_1 + b \cdot \left( x_1 - \lfloor a/b \rfloor \cdot y_1 \right) = ga⋅y1​+b⋅(x1​−⌊a/b⌋⋅y1​)=g

对比我们希望得到的式子 a⋅x+b⋅y=ga\cdot x + b\cdot y = ga⋅x+b⋅y=g,我们可以令:

x=y1,y=x1−⌊a/b⌋⋅y1x = y_1, \quad y = x_1 - \lfloor a/b \rfloor \cdot y_1x=y1​,y=x1​−⌊a/b⌋⋅y1​

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

这个公式可以这样记忆:​递归返回的系数中,新的 xxx 是旧的 y1y_1y1​,新的 yyy 是旧的 x1x_1x1​ 减去商乘以旧的 y1y_1y1​​​。

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

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

递归层 a b a % b 递归返回 (g, x1, y1) 计算新 (x, y) 本层结果
1 6 10 6 来自下层 见下
2 10 6 4 来自下层
3 6 4 2 来自下层
4 4 2 0 来自下层
5 2 0 — (2, 1, 0) 直接返回 — (2,1,0)

现在逐层向上回溯:

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

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


3. 通解与更多例子

上面得到的只是一组特解​​。实际上,如果 x0,y0x_0, y_0x0​,y0​ 是一组解,那么所有整数解可以写成:

x=x0+bg⋅t,y=y0−ag⋅t(t为任意整数)x = x_0 + \frac{b}{g} \cdot t, \quad y = y_0 - \frac{a}{g} \cdot t \quad (t \text{为任意整数})x=x0​+gb​⋅t,y=y0​−ga​⋅t(t为任意整数)

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

例如对于 6x+10y=26x+10y=26x+10y=2,g=2g=2g=2,bg=5\frac{b}{g}=5gb​=5,ag=3\frac{a}{g}=3ga​=3,特解 x0=2,y0=−1x_0=2, y_0=-1x0​=2,y0​=−1,通解为:

x=2+5t,y=−1−3tx = 2 + 5t, \quad y = -1 - 3tx=2+5t,y=−1−3t

当 t=0t=0t=0 时就是 (2, -1);t=1t=1t=1 时得到 (7, -4),验证:6×7+10×(−4)=42−40=26\times 7 + 10\times(-4)=42-40=26×7+10×(−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 对于正数是向下取整,正好是公式所需的 ⌊a/b⌋\lfloor a/b \rfloor⌊a/b⌋。但如果 a 或 b 出现负数,结果可能不同(向下取整 vs 向零取整)。扩展欧几里得通常只处理非负整数,如果遇到负数,可以先取绝对值或者用其他处理方式,初学者建议先只处理正数。
  4. 返回值理解错误​​:有些同学以为返回的 x, y 是唯一的,实际上只是一组​特解。要得到所有解,需要使用通解公式。
  5. 对递归深度没有概念​​:递归的深度不超过 O(log⁡min⁡(a,b))O(\log \min(a,b))O(logmin(a,b)),一般不用担心栈溢出,但如果是竞赛中数据极大(比如 101810^{18}1018),深度也只有几十层,安全。

5. 完整代码示例(含详细中文注释)

C++ 实现

cpp
#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 实现

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 之后可以学什么?

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

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

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

同类知识点