扩展欧几里得算法（exgcd）在求 GCD 的同时得到贝祖系数 x, y 使 ax + by = gcd(a,b)。它是求解模逆元、线性同余方程的基础工具。
一、贝祖定理
对任意整数 a, b，存在整数 x, y 使得：
ax + by = gcd(a, b)
二、扩展欧几里得算法
递归推导
gcd(a, b) = gcd(b, a mod b)
设 bx' + (a mod b)y' = gcd(b, a mod b)
bx' + (a - ⌊a/b⌋·b)y' = gcd
ay' + b(x' - ⌊a/b⌋·y') = gcd
所以: x = y', y = x' - ⌊a/b⌋·y'
实现
// 返回 gcd(a, b)，同时 x, y 满足 ax + by = gcd(a,b)
long[] exgcd(long a, long b) {
if (b == 0) return new long[]{a, 1, 0}; // gcd=a, x=1, y=0
long[] res = exgcd(b, a % b);
long gcd = res[0], x1 = res[1], y1 = res[2];
long x = y1;
long y = x1 - (a / b) * y1;
return new long[]{gcd, x, y};
}迭代版本
long[] exgcdIter(long a, long b) {
long x0 = 1, y0 = 0, x1 = 0, y1 = 1;
while (b != 0) {
long q = a / b;
long tmp = a % b; a = b; b = tmp;
tmp = x0 - q * x1; x0 = x1; x1 = tmp;
tmp = y0 - q * y1; y0 = y1; y1 = tmp;
}
return new long[]{a, x0, y0};
}