Python用欧几里得求逆元的方法

这篇文章主要介绍Python用欧几里得求逆元的方法，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

目前累计服务客户近千家，积累了丰富的产品开发及服务经验。以网站设计水平和技术实力，树立企业形象，为客户提供成都网站设计、成都做网站、网站策划、网页设计、网络营销、VI设计、网站改版、漏洞修补等服务。成都创新互联公司始终以务实、诚信为根本，不断创新和提高建站品质，通过对领先技术的掌握、对创意设计的研究、对客户形象的视觉传递、对应用系统的结合，为客户提供更好的一站式互联网解决方案，携手广大客户，共同发展进步。

Python用欧几里得求逆元的方法：

建立一个带参数返回值的函数，编写求逆元的一次算法，采用递归的方式循环调用函数，递归直至余数等于零。调用该函数，将需要求的数值带入进去，执行该函数就可以了

示例代码如下:

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

执行结果如下：

ext_gcd(1848,701)
>>> (-11, 29, 1)

以上是Python用欧几里得求逆元的方法的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注创新互联行业资讯频道！

本文标题：Python用欧几里得求逆元的方法
网站路径：http://mswzjz.cn/article/jcppec.html