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

问题：求两个正整数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

  

   

    

     

    
    

     

      def gcd(a, b):
     
    
   

    

     

    
    

     
 while a != 0:
     
    
   

    

     

    
    

     

       a, b = b % a, a
     
    
   

    

     

    
    

     
 return b
     
    
  
 

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

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

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

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

  

   

    

     

    
    

     

      //返回 d=gcd(a,b); 和对应于等式 ax+by=d 中的 x,y
     
    
   

    

     

    
    

     

      long long extend_gcd(long long a,long long b,long long &x,long long &y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(a==0&&b==0) return −1;//无最大公约数
     
    
   

    

     

    
    

     
 if(b==0){x=1;y=0;return a;}
     
    
   

    

     

    
    

     
 long long d=extend_gcd(b,a%b,y,x);
     
    
   

    

     

    
    

     

       y−=a/b*x;
     
    
   

    

     

    
    

     
 return d;
     
    
   

    

     

    
    

     

      } 
     
    
  
 

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

  

   

    

     

    
    

     
 //********* 求逆元 *******************
     
    
   

    

     

    
    

     

      //ax = 1(mod n)
     
    
   

    

     

    
    

     

      long long mod_reverse(long long a,long long n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 long long x,y;
     
    
   

    

     

    
    

     
 long long d=extend_gcd(a,n,x,y);
     
    
   

    

     

    
    

     
 if(d==1) return (x%n+n)%n;
     
    
   

    

     

    
    

     
 else return −1;
     
    
   

    

     

    
    

     

      } 
     
    
  
 

逆元，利用欧拉：

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

  

   

    

     

    
    

     

      long long inv(long long a,long long mod)//为素数mod
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return pow_m(a,mod−2,mod);
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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