扩展欧几里得+求解逆元

ゝ一世哀愁。 2022-05-16 22:26 152阅读 0赞

在为扩展前，什么是欧几里得算法？？

欧几里得又称辗转相除法，用于计算两个整数a,b的最大公约数（最大公约数：指两个或多个整数共有约数中最大的一个）其计算原理依赖于下面的定理：

gcd函数就是用来求(a,b)的最大公约数的。

gcd函数的基本性质：

gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|)

### 公式表述 ###

gcd(a,b)=gcd(b,a mod b)

证明：a可以表示成a = kb + r，则r = a mod b

假设d是a,b的一个公约数，则有

d|a, d|b，而r = a - kb，因此d|r

因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数，则

d | b , d |r ，但是a = kb +r

因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

代码实现：

int gcd(int a,int b)
    {
        int c;
        while(b!=0)
        {
            c=a%b;
            a=b;
            b=c;
        }
        return a;
    }

扩展欧几里得：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

验证：我们知道gcd(a,b)=gcd(b,a%b)；所以我们可以得到：bx1+a%by1=ax+by;

化简后可以到bx1+(a-a/b\*b)y1=ay1+b(x1-a/by1)=ax+by;

这里我们令**x=y1**;所以可以得到解：**y=x1-a/by1;**

**对于关于x，y的方程ax+by=g来说，让x增加b/g，让y减少a/g，等式两边还相等**

所以我们可以计算出所有的解，但是b到最后可能会为0，所以到b=0的时候停止求解

那么对于方程a \* x + b \* y = c 来说，它的解怎么求呢？   
答：如果c % gcd(a,b) != 0，即c不是gcd的整数倍，则无解。   
如果c % gcd(a,b) == 0 且 c / gcd(a,b) = t，那么求出方程 a \* x + b \* y = gcd(a,b)的所有解x,y，将x,y乘上t，对应的x’,y’即是方程a \* x + b \* y = t \* gcd(a,b)的解

## 直接说吧,假设**d=gcd(a,b). 那么x=x0+b/d\*t; y=y0-a/d\*t;**其中t为任意常整数。 ##

### 推导过程：由题意可得a\*x0+ab/d+b\*y0-ab/d=d; ###

### 得到:a(x0+b/d)+b(y0-a/d)=d; ###

### 因为这是不等式所以得到：x=x0+b/d\*t,y=y0-a/d\*t,t为常数 ###

大概就是这样

代码：

int gcd(int a,int b,int &x,int &y)
    {
        if(a==0&&b==0)
            return -1;//无最大公约数
        if(b==0)
        {
            x=1;
            y=0;
            return a;//返回最大公约数
        }
        int d=gcd(b,a%b,y,x);
        y-=a/b*x;
        return d;
    }

可能有的人对于为什么x，y要加取地址符不是很清楚，这里给出一个代码对比应该就能理解了

样例1：没有取地址符的

![70][]

样例2：有取地址符

![70 1][]

那么扩展欧几里得有什么用呢？？？可以用它求如下的问题：

形如ax+by=c这样的数或者让你求逆元，逆元就是ax同余（1modb）这里面x的最小正整数即为逆元

a同余（1%b）就等价于ax+by=1解这个方程即可

注意这里的gcd=1，也就是说当两数互质的时候存在解，然后还需要注意这里b可能为非正整数所以需要取正。

代码：

ll cal(ll a,ll b)///求逆元
    {
        ll x,y;
        ll gcd=exgcd(a,b,x,y);
        if(1%gcd)
            return -1;///无解的情况
        x*=1/gcd;
        b=abs(b);
        ll ans=x%b;
        if(ans<=0)
            ans+=b;
        return ans;
    }

[70]: /images/20220517/a561c08bd57048aeb123a0fdbe2876a5.png
[70 1]: /images/20220517/4ba35bc8878b4e449824073c3f88b66c.png