扩展GCD算法(扩展欧几里得算法)(扩展辗转相除法)(贝祖算法)代码模板（C/C++/Java/Python多版本）

扩展GCD算法(扩展欧几里得算法)(扩展辗转相除法)(贝祖算法)代码模板（C/C++/Java/Python多版本）并不只看表面做法，关键还要理解相关条件、限制和后续影响。

扩展欧几里得算法是欧几里得算法的推广，它在计算两个整数最大公约数（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)三元组