扩展欧几里得算法原理

扩展欧几里得算法是一种用于求解两个整数的最大公约数以及对应的贝祖等式的算法。其原理如下：

给定两个非负整数a和b，我们要找到它们的最大公约数gcd(a, b)以及满足贝祖等式ax + by = gcd(a, b)的整数解(x, y)。

1. 初始化变量x1=1，y1=0，x2=0，y2=1，用于保存上一次迭代的结果。
2. 当b不等于0时，执行以下步骤：
- 计算商q和余数r，使得a = bq + r。
- 更新a为b，b为r。
- 更新变量x1、y1、x2、y2，使得x1 = x2，y1 = y2，x2 = x1 - qx2，y2 = y1 - qy2。
3. 当b等于0时，迭代结束。此时a即为最大公约数gcd(a, b)，而x1和y1即为贝祖等式的解。

通过不断进行欧几里得算法的迭代过程，我们可以找到最大公约数以及对应的贝祖等式的解。这种算法的时间复杂度为O(log(min(a, b)))。

需要注意的是，扩展欧几里得算法要求输入的两个整数必须是非负的。如果输入的整数中存在负数，可以通过将其转换为非负整数进行求解。