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

扩展欧几里得算法

image-20210507002724344

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

伪码:

 在求解 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; ]

源码:

// 传入引用,随时更改值并返回!
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

思路:

image-20210519020351068

Ps:Bezout即是裴蜀定理

源码:

#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 + 2 =
快来做第一个评论的人吧~