6、编程实现扩展欧几里德算法，要求： 1）输入两个正整数r0和r1，r0 > r1；r0的二进制位数不超过15位； 2）输出(r0，r1)； 3）输出整数s和t，使得sr0 + tr1 = (r0，r1)； 4）不准使用数组，不准使用递归；

扩展欧几里得算法是一种用于求解最大公约数（GCD）及其贝祖等式系数的算法。给定两个正整数 r0 和 r1（其中 r0 > r1），其二进制表示长度不超过15位，我们可以按照以下步骤来编写非递归的扩展欧几里得算法：

1. 定义函数 gcd(a, b)，返回a和b的最大公约数。
2. 初始化变量：初始gcd为r0，prev_gcd为r1，s为0，t为1（因为根据贝祖等式 sr0 + tr1 = (r0, r1)，当r1=0时，s=1，t=0）。
3. 当r1不等于0时，执行循环：
a. 计算新的prev_gcd（即上一步的gcd），等于 prev_gcd % r1。
b. 更新s和t，它们按比例缩放：s = s - (prev_gcd // r1) * t。
t = t + (prev_gcd // r1) * s。
c. 将r0和r1更新为prev_gcd和r1。
4. 循环结束后，prev_gcd就是两数的最大公约数，s和t满足sr0 + tr1 = gcd(r0, r1)。

以下是该算法的伪代码实现：

def extended_euclidean_algorithm(r0, r1):
    def gcd(a, b):
        while b != 0:
            a, b = b, a % b
        return a

    if r0 < r1:
        r0, r1 = r1, r0
    prev_gcd = r1
    s, t = 1, 0

    while r1 != 0:
        quotient = prev_gcd // r1
        r0, r1 = r1, r0 - quotient * r1
        s, t = t, s - quotient * t

    return prev_gcd, s, t

# 测试
r0 = 397  # 示例数字
r1 = 181
result = extended_euclidean_algorithm(r0, r1)
print(f"GCD: {result[0]}, coefficients: (s={result[1]}, t={result[2]})")