欧几里得gcd/extend_gcd

举报
兔老大 发表于 2021/05/07 03:32:19 2021/05/07
【摘要】 正式叙述前还写了一点自己的小感受。 问题:求两个正整数a,b的最大公约数。 大神看来是很简单的问题,但是对于去年夏天刚学python的我来说,这是个很难的问题,还记得当时一晚上睡不着都在想怎么快一点的求出最大公约数,后来猜测最小公倍数的求法,还有最后想出来的欣喜若狂,我现在还记忆犹新。   还记得看过一个小梗:一个农民种着种着地,一排一排的种,突然陷入深思,...

正式叙述前还写了一点自己的小感受。

问题:求两个正整数a,b的最大公约数

大神看来是很简单的问题,但是对于去年夏天刚学python的我来说,这是个很难的问题,还记得当时一晚上睡不着都在想怎么快一点的求出最大公约数,后来猜测最小公倍数的求法,还有最后想出来的欣喜若狂,我现在还记忆犹新。

 

还记得看过一个小梗:一个农民种着种着地,一排一排的种,突然陷入深思,沉思良久,回去算了很久以后,借了钱疯了似的坐火车跑到中科院门口,等来数学系教授,向他讲述了自己的重大发现。大概意思就是,自己从田地中大彻大悟,发明了一种快速计算方法,不用计数,不用加法,不用数学,还给了教授一张伟大的定律表。

教授告诉他:你真的很厉害,你的发现很伟大,能在种田中悟出来这种算法可不容易。

 

 

 

 

 

 

 

但是,你发明的这种算法叫乘法,你给我的表,完善一下以后,叫九九乘法表。

农民继续回去种田

(这个故事告诉我们要多虚心接受知识,不要老自己想。。。。)

 

我知道了欧几里得算法以后,感觉自己就跟这个农民一样。。。。。。。

不过,知道了自己的想法就是欧几里得算法时,还是挺高兴的。。。

就当锻炼思维了吧。。只能这么安慰自己。

 

好,开始正题。。。。::

 

我当时的思路是这样的:求a,b的最大公约数,假设最大公约数是x的话,a一定可以用i*x来表示,b也一定可以用j*x来表示,我们怎么把i和j去掉,把x榨出来呢??

让这俩数不断互相相减就可以啦!

后来自己想到了互相取余。

 

我们来看正规的欧几里得算法:

首先放简介:欧几里德算法又称辗转相除法,是指用于计算两个正整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

看代码实现:

Python


  
  1. def gcd(a, b):
  2. while a != 0:
  3. a, b = b % a, a
  4. return b

 

后来知道了欧几里得还有拓展:

可以用来求二元一次方程的通解,还可以用来求乘法逆元。 

已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足贝祖等式ax+by=gcd(a,b)

如果a是负数,可以把问题转化成|a|(-x)+by=gcd(|a|,b) ,然后令x'=(-x)。


  
  1. //返回 d=gcd(a,b); 和对应于等式 ax+by=d 中的 x,y
  2. long long extend_gcd(long long a,long long b,long long &x,long long &y)
  3. {
  4. if(a==0&&b==0) return1;//无最大公约数
  5. if(b==0){x=1;y=0;return a;}
  6. long long d=extend_gcd(b,a%b,y,x);
  7. y−=a/b*x;
  8. return d;
  9. }

求逆元,真的不想叙述了,上个代码算了


  
  1. //********* 求逆元 *******************
  2. //ax = 1(mod n)
  3. long long mod_reverse(long long a,long long n)
  4. {
  5. long long x,y;
  6. long long d=extend_gcd(a,n,x,y);
  7. if(d==1) return (x%n+n)%n;
  8. else return1;
  9. }

逆元,利用欧拉:

mod 为素数, 而且 a 和 m 互质 


  
  1. long long inv(long long a,long long mod)//为素数mod
  2. {
  3. return pow_m(a,mod−2,mod);
  4. }

 

 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/81675417

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。