[数论](5)扩展欧几里得

扩展欧几里得算法

裴蜀定理:有任意正整数a与b,存在x和y,使得ax+by=gcd(a,b)

伪码:

```C++ 在求解 gcd(a, b) 的过程中顺便求解两个系数x , y：

1. 当 b == 0 时, 即 a x + 0 y = gcd(a, 0) = 0 即 x = 1, y = 0 即可！
2. 当 b != 0 时： 由于：gcd(a, b) == gcd(b, a % b) 即：a x + b y = gcd(a, b) --> b y + a % b x = gcd(b, a % b)
   （注：根据 x 与 y 的对应关系写出！） 由 a % b == a - a / b b，则该式变为：b y + (a - a / b b) x = gcd(b, a % b); 化简得：a x + b (y - a / b x) = gcd(b, a % b); 对应相等, 发现：x 没有变，y 减少了 a / b x：即 [ y -= a / b * x; ]

源码:

```C++ // 传入引用，随时更改值并返回！ int exgcd(int a, int b, int & x, int & y){ if(b == 0){ // 1. 第一种情况： x = 1, y = 0; return a; } // 注意：这里y与x互换，是为了计算方便！不换也可以，用其他变量代替，化简完后根据对应相等再换回去即可！ int t = exgcd(b, a % b, y, x); // 2. 第二种情况 y -= a / b * x; return t; }

**扩展欧几里得的应用 (求解线性同余方程)**

![image-20210519020338709](https://i.loli.net/2021/05/19/EWd1iJYyOtDTgB9.png)

思路:

![image-20210519020351068](C:\Users\Axuan\AppData\Roaming\Typora\typora-user-images\image-20210519020351068.png)

Ps:Bezout即是裴蜀定理

源码:

```C++
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int exgcd(int a,int b,int &x,int &y){//扩展欧几里得模板
    if(b==0){
        x=1;y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y= y - a / b * x;
    return d;
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int a,b,m;
        scanf("%d %d %d",&a,&b,&m);
        int x,y;
        int d=exgcd(a,m,x,y);
        if(b%d) printf("impossible\n");
        else printf("%lld\n",(long long)x*(b/d)%m);
    }
    return 0;
}

扩展欧几里得的应用(求乘法逆元)

当n不是质数时，可以用扩展欧几里得算法求逆元： a有逆元的充要条件是a与p互质，所以gcd(a, p) = 1 假设a的逆元为x，那么有a * x ≡ 1 (mod p) 等价：ax + py = 1 逆元 = exgcd(a, p, x, y)

本文链接：