python语言编程欧几里得算法及扩展欧几里得算法

欧几里得算法：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

代码如下：

def gcd(a,b):
# *************begin************#
    if a<b:
        t=a
        a=b
        b=t
    while a%b!=0:
        temp=a%b
        a=b
        b=temp
    return b

# **************end*************#
a = int(input())
b = int(input())
r = gcd(a,b)
print(r)
           

测试输入：

1234

4321

预期输出：

1

测试输入：

1769

550

预期输出：

1

测试输入：

55

15

预期输出：

5

扩展欧几里得算法：已知整数a、b`，设计扩展欧几里得算法，如果a和b不互素，输出None；如果a和b互素，输出二者的乘法逆元，注意不限定a和b的大小顺序

思路如下：

代码如下：

def extendGcd(m, b):
    if m < b:
        t = m
        m = b
        b = t
    x1, x2, x3 = 1, 0, m
    y1, y2, y3 = 0, 1, b
    while True:
        if y3 == 0:
            return 'None'
            break
        elif y3 == 1:
            return y2 % m
            break
        else:
            Q = x3 // y3
            t1, t2, t3 = x1 - Q * y1, x2 - Q * y2, x3 - Q * y3
            x1, x2, x3 = y1, y2, y3
            y1, y2, y3 = t1, t2, t3


a = int(input())
b = int(input())
r = extendGcd(a, b)
print(r)
           

测试输入：

1769

550

预期输出：

550

测试输入：

550

1750

预期输出：

355

测试输入：

55

15

预期输出：

None

‘’’