扩展欧几里得算法

扩展欧几里得算法是求解两个整数 a 和 b 的最大公约数 gcd(a, b) 的一种算法。此算法同时计算出了 a 和 b 的一组贝祖等式的解，即 ax + by = gcd(a, b)。

具体步骤如下：

1. 初始化 a1 = 1, b1 = 0, a2 = 0, b2 = 1, r1 = a, r2 = b。

2. 用辗转相除法求出 r1 除以 r2 的商 q 和余数 r3。

3. 计算 a3 = a1 - qa2, b3 = b1 - qb2。

4. 如果 r3 = 0，则算法结束，此时 gcd(a, b) = r2，ax + by = r2 的一组解为 (x, y) = (a2, b2)。

5. 如果 r3 ≠ 0，则令 r1 = r2, r2 = r3, a1 = a2, a2 = a3, b1 = b2, b2 = b3，并返回第2步。

Python 代码实现如下：

def extended_euclidean_algorithm(a, b):
    # 初始化
    a1, b1, a2, b2 = 1, 0, 0, 1
    r1, r2 = a, b

    while r2 != 0:
        # 辗转相除法
        q, r3 = divmod(r1, r2)

        # 计算新的 a 和 b
        a3, b3 = a1 - q * a2, b1 - q * b2

        # 更新变量
        r1, r2 = r2, r3
        a1, a2 = a2, a3
        b1, b2 = b2, b3

    # 返回 gcd 和解
    return r1, a1, b1

使用该算法可以求出两个整数的最大公约数以及一组贝祖等式的解。