欧几里得+扩展欧几里得（理解）

妖狐艹你老母 2022-06-05 05:39 317阅读 0赞

--------------------

## **欧几里得：** ##

--------------------

辗转相除法  
代码：

typedef long long LL;  
    
    LL gcd(LL a, LL b) {
        return b == 0 ? a : gcd(b, a%b);
    }

**用途：**是一个求最大公约数的计算方法；

**自己的理解：**对于传入的数值进行判定，是否b位置为0（因为b随着调用会改变），如果不为0继续调用，a，b的值进行变换，  
如果为0，返回a位置的值；

看起来与最大公约数无关，其实不然，首先想一想什么是最大公约数，是一个能被这a，b两个数整除的一个数，一定比a，b都小，假设a%b==0，那么存在一个x，使得a=bx，我们不管x的值为多少，但是a对b取余，和b对b取余，都为0，那么b就是它的一个公约数，现在不能保证一定是最大公约数。

如果我们从ab之间最小的那个开始判定（先假设a%b==0），假如a>b，那么b一定是a，b的最大公约数，例如：8和4，4为8，4的最大公约数。

我们得到一个结论：如果a%b==0，那么b为a，b的公约数。

我们去掉这个假设a%b!=0呢，我们知道，如果a%b!=0（a>b），a中包含b所没有的素数（每个正整数都可以唯一表示成素数的乘积），利用这个思想，我们把a中b没包含的素数剔除（a%b），这样一来，b一定比a%b大，但是这也不能一定说明，b%（a%b）为0，还是需要判定。

然后继续调用函数，把a，b的值重新定义，现在的a，b已经不是上一次的a，b了，叫做a1，b1，继续做a1%b1的判定，直到ax%bx==0，现在的bx一定是最大公约数，因为bx是从大到小开始判定的。

有一个问题出来了，ax%bx一定会有等于0的时候吗，答案是一定的，因为1是所有数的因数，两个素数的最大公约数就是1，一次次的取余，互换位置，最终的结果就是ax=1，bx=1，然后取余为0，返回了a的值 1。

--------------------

## **扩展欧几里得：** ##

--------------------

代码：

typedef long long LL;  
    
    LL extgcd(LL a, LL b, LL &x, LL &y) {
        LL d = a;
        if(b != 0) {
            d = extgcd(b, a%b, y, x);
            y -= (a / b) * x;
        } else {
            x = 1; y = 0;
        }
        return d;
    }

**用途：**对于二元一次方程组的求解：ax+by=1；  
**自己的理解：**先思考一个问题，如果ax+by=1成立，那么a，b的最大公约数为1，也就是说gcd（a，b）==1，说明当gcd（a，b）！=1，a，b不互质，方乘无解。  
从代码上看，其中有gcd的东西，不一样的是，这个需要一直算到b=0，才会停止，然后执行 y -= (a / b) \* x，这里的过程类似于递归，每次a，b交换，x，y跟着交换，最后求答案的时候，逆着过程来一遍，就可以得到答案了。  
\*\*例子：\*\*6x+4y=1（6，4，x，y）

6x+4y=1（6，4，x，y）
    d = 6;
    b != 0; 
    d = 4y + 2x;（4，2，y，x）//调用函数，{}里都是函数执行的内容，注意这里是y，x
    {
        d = 4;             
        b != 0;             //if里的判定
        d = 2x（2，0，x，y）  //调用函数，{}里都是函数执行的内容
        {
            d = 2;
            b == 0;         //执行了else的内容
            x = 1, y = 0;
            return d=2;     //返回
        }
        y = y - (a / b) * x = 1 - 2 * 0 = 1;//这里为什么y=1呢，问题1（见下分析）
        return d=2;
    }
    y = y - (a / b) * x = 0 - 1 * 1 = -1;   //这里才是对上的x，y的值
    return d=2;             //d在函数一开始的时候定义了，第一次返回是多少就是多少

**问题1：**为什么我要x=1，y=0，而调用的时候是y=1呢，仔细观察源代码，在调用的时候d = extgcd(b, a%b, y, x);，这里x，y的位置互换了，加了&，各自是各自对应的值，每次调用都会互换位置，其中很复杂，必须模拟程序的时候仔细分析才行，不管怎么样，代码就在那里，这里不清楚也没关系。

顺便说一下返回的d就是欧几里得最大公约数。

说完这个例子是不是更好理解这个欧几里得了呢。

--------------------

## **然后推广一下，ax+by=c的情况** ##

如果变成ax+by=c的话，解的组数会有很多个，一般题目会要求输出一个数对于另一个数的乘法逆元之类的。

什么是乘法逆元？  
a\*x ≡ 1（mod m）  
意思就是 a\*x % m == 1，它的意思大致就是使x的值变小，但是要非负。

考虑这个问题之前，需要知道，什么时候无解，△？太麻烦了。如果数字很大，就会爆数据。

前面判定有没有解是gcd（a，b）！=1， 的时候无解，也就是说gcd（a，b）==1的时候有解，现在把1换成了c，gcd（a，b）==c？肯定不可以，gcd返回的是一个约数，而且是最大的，c完全也是其中一个小一点的约数。

聪明的你也许已经看出来了，只要abc的约数一致就可以了，令d=gcd（a，b）  
判定gcd（d，c）==0，更简单的表达

## **c % gcd（a，b） == 0** ##

**反之无解。**

话不多说先贴代码

typedef long long LL;  
    
    LL extgcd(LL a, LL b, LL &x, LL &y) {
        if(!b) {
            x = 1;
            y = 0;
            return a;   
        }
        LL ans = extgcd(b, a%b, x, y);
        LL t = x;
        x = y;
        y = t - a / b * y;
        return ans;
    }
    
    LL cal(LL a, LL b, LL c) {
        LL x, y;
        LL d = extgcd(a, b, x, y);
        if(c % d != 0) return -1;
        x = x * c / d;          //①
        b /= d;                 //②
        if(b < 0) b = -b;       
        LL ans = x % b;         //③
        if(ans <= 0) ans += b;
        return ans;
    }

①：c是结果，d是a，b的最大公约数，c可能是比d小的公约数，所以c/d是扩大/缩小的倍数，x乘上，就是与c一致的倍数，也就是ax+by==c成立的时候，x的最大值。  
②：b中有多少个d  
③：除去x中新b的部分

为什么要这样做呢  
因为知道了x ，y也就知道了，所以这里只对x操作。  
把x中b可以替换的部分拿去b，减少x的值，变相的增加了y的值，在成立的基础上，减小x，增大y。

得到的ans就是x的值，y利用已知就可以得到了。