欧几里得gcd/extend_gcd

分手后的思念是犯贱 2022-05-16 02:59 141阅读 0赞

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

问题：求两个[正整数][Link 1]a，b的[最大公约数][Link 2]。

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

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

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

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

农民继续回去种田

（这个故事告诉我们要多虚心接受知识，不要老自己想。。。。）

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

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

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

# 好，开始正题。。。。：： #

#  #

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

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

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

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

首先放简介：欧几里德算法又称[辗转相除法][Link 3]，是指用于计算两个[正整数][Link 1]a，b的[最大公约数][Link 2]。应用领域有数学和计算机两个方面。计算公式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的[最大公约数][Link 2]的同时，能找到整数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);
    }

[Link 1]: https://baike.baidu.com/item/%E6%AD%A3%E6%95%B4%E6%95%B0/8461335
[Link 2]: https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0/869308
[Link 3]: https://baike.baidu.com/item/%E8%BE%97%E8%BD%AC%E7%9B%B8%E9%99%A4%E6%B3%95/4625352