扩展欧几里得算法是欧几里得算法的推广，它在计算两个整数最大公约数（gcd）的同时，通过回溯或迭代过程中的系数递推，求得一组满足贝祖等式（两个整数的最大公约数总可以表示为它们的线性组合） ax + by = gcd(a, b) 的整数解 (x, y)；这一对系数也称为贝祖系数，是求解模逆元、线性同余方程以及许多密码学与数论问题的基础工具。
1. C/C++版代码：
long long extgcd(long long a, long long b, long long &x, long long &y) {
// 递归终止条件：b=0时，gcd=a，系数x=1,y=0满足a*x+b*y=gcd
if (b == 0) {
x = 1;
y = 0;
return a;
}
// 递归计算gcd和系数，然后调整贝祖等式系数
long long d = extgcd(b, a % b, x, y);
long long t = x; // 暂存上层递归的x值
x = y; // 当前递归x = 上层递归y
y = t - a / b * y; // 当前递归y = 上层递归x - a/b * 上层递归y
return d; // 返回最大公约数
}2. Java版代码：
public class ExtendedGCD {
// 封装扩展欧几里得算法的结果：d=gcd(a,b)及贝祖等式系数x,y
public static class Result {
public long d; // 最大公约数
public long x; // 贝祖等式系数x
public long y; // 贝祖等式系数y
public Result(long d, long x, long y) {
this.d = d;
this.x = x;
this.y = y;
}
}
// 扩展欧几里得算法：计算gcd(a,b)及满足ax+by=gcd(a,b)的整数解(x,y)
public static Result extgcd(long a, long b) {
// 递归终止：b=0时，gcd=a，x=1,y=0满足a*x+0*y=a
if (b == 0) {
return new Result(a, 1, 0);
}
// 递归计算并回溯调整系数
Result res = extgcd(b, a % b);
long t = res.x; // 暂存上层递归的x
res.x = res.y; // 当前x = 上层y
res.y = t - (a / b) * res.y; // 当前y = 上层x - (a/b)*上层y
return res;
}
}3. Python版代码：
def extgcd(a, b): # 扩展欧几里得算法：计算最大公约数d及满足ax+by=d的整数解(x,y) # 递归终止条件：b=0时，gcd=a，x=1,y=0满足ax+0y=a if b == 0: return a, 1, 0 # 递归计算并回溯调整系数 d, x1, y1 = extgcd(b, a % b) # x1,y1是递归下层的解 x = y1 # 当前x = 下层的y y = x1 - (a // b) * y1 # 当前y = 下层的x - (a//b)*下层的y return d, x, y # 返回(d,x,y)三元组
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程