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

扩展欧几里得算法

image-20210507002724344

裴蜀定理:有任意正整数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)

本文链接:

https://nullcode.fun/143.html
1 + 3 =
快来做第一个评论的人吧~