def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y)

这是一个求解最大公约数的扩展欧几里得算法，返回一个三元组 (gcd, x, y)，其中 gcd 是 a 和 b 的最大公约数，x 和 y 满足 ax + by = gcd。

具体来说，算法在每一次递归中通过取模操作将 b 对 a 取余数，然后交换 b 和 a 继续递归，直到 a 等于 0 为止。递归回溯过程中，根据递推公式 x[i-2] - (b[i-1] // a[i-1]) * x[i-1] = y[i-2] 和 y[i-2] - (b[i-1] // a[i-1]) * y[i-1] = x[i-1]，计算出当前 gcd、x 和 y 的值，并返回。