扩展欧几里得算法 定义 扩展欧几里得算法是用来在已知整数 a、b 的情况下，求解一组整数 x、y 使得 ax + by = gcd(a, b)（gcd 表示最大公约数）。 运用情况 求解线性同余方程。在密码学等领域有广泛应用。 注意事项 要注意边界情况和特殊值的处理。在计算过程中要注意数据的范围，避免溢出。 解题思路 通过递归的方式不断缩小问题规模。从较大的数对(a, b)逐步递推