扩展欧几里得算法求逆元python代码实现(含递归与非递归算法)

概述扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。通常谈到最大公因子时,我们都会提到一个非常基本的事实:给予二整数a与b,必存在有整数x与y使得ax+by=gcd(a,b)。因此，有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数；然后，收集辗转相除法中产生的式子

扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。因此，有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数；然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的一组整数特解。

以下是扩展欧几里得算法的python实现：

1.递归

#扩展欧几里得算法 def ext_gcd(a, b):        if b == 0:                  return 1, 0, a         else:                 x, y, gcd = ext_gcd(b, a % b) #递归直至余数等于0(需多递归一层用来判断)                x, y = y, (x - (a // b) * y) #辗转相除法反向推导每层a、b的因子使得gcd(a,b)=ax+by成立                 return x, y, gcd

2.非递归

print("请输入一个整数：")a = int(input())print("请输入模？")m = int(input())if a < m:    a, m = m, a    x1, x2,x3= 1, 0, a    y1, y2,y3= 0, 1, m    while y3 != 0:        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    print(x2)else:    x1, x2, x3 = 1, 0, a    y1, y2, y3 = 0, 1, m    while y3 != 0:        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    print(x1)

以下是两种方法的运行验证结果

说明以上代码正确有效。

总结

以上是内存溢出为你收集整理的扩展欧几里得算法求逆元python代码实现(含递归与非递归算法)全部内容，希望文章能够帮你解决扩展欧几里得算法求逆元python代码实现(含递归与非递归算法)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。