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

扩展欧几里得算法

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

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

思路:

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)

本文链接：