扩展欧几里得算法(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. 新手容易犯的错误
- 递归参数顺序搞反:有些同学在递归调用时写成
exgcd(a % b, b)而不是exgcd(b, a % b)。注意欧几里得算法是gcd(a,b) = gcd(b, a%b),所以递归时第一个参数是b,第二个是a % b,顺序不能错。 - 忘记用临时变量保存 x1, y1:在递归返回后,必须先保存
x1和y1,然后再计算当前层的x和y。如果直接用当前层的x和y去接收递归结果,会导致公式计算混乱(因为x的值被覆盖了)。 - 整数除法取整问题:在 C++ 中
a / b对于正数是向下取整,正好是公式所需的 ⌊a/b⌋\lfloor a/b \rfloor⌊a/b⌋。但如果a或b出现负数,结果可能不同(向下取整 vs 向零取整)。扩展欧几里得通常只处理非负整数,如果遇到负数,可以先取绝对值或者用其他处理方式,初学者建议先只处理正数。 - 返回值理解错误:有些同学以为返回的
x, y是唯一的,实际上只是一组特解。要得到所有解,需要使用通解公式。 - 对递归深度没有概念:递归的深度不超过 O(logmin(a,b))O(\log \min(a,b))O(logmin(a,b)),一般不用担心栈溢出,但如果是竞赛中数据极大(比如 101810^{18}1018),深度也只有几十层,安全。
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 之后可以学什么?
扩展欧几里得算法是数论里的螺丝刀,它拧开了好几扇门:
- 求模逆元:在模 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 的倍数),以及 最小正整数解 的求法。推荐动手画一画递归树,更直观地理解系数是如何“传递”的。