题解 | 【模板】扩展欧几里得算法求解乘法逆元 #

$[模板+扩展欧几里得]$

对于整数 $a,m$ ，若存在整数 $x$ 满足： $a\times x\equiv1(mod\ m)$ ，则称 $x$ 是 $a$ 在模 $m$ 意义下的乘法逆元，记为 $a^{-1}$

首先，求解乘法逆元的方法有两种：

方法一：费马小定理

使用该方法的前提是： $m$ 必须是质数，并且 $a$ 与 $m$ 互质( $a$ 不是 $m$ 的倍数)

费马小定理内容：

如果 $m$ 是质数，那么对任意与 $m$ 互质的整数 $a$ ，有 $a^{m-1}\equiv1(mod\ m)$ c成立

那么 $a\times a^{m-2} \equiv1(mod \ m)$ ，所以 $x=a^{m-2}\ mod \ m$ ，即可用快速幂方法

方法二：扩展欧几里得

使用该方法的前提是：仅需要 $a$ 与 $m$ 互质

扩展欧几里得用于求解线性不定方程 $ax+my=gcd(a,m)$ 的一组整数解 $(x,y)$

当 $a$ 与 $m$ 互质，即 $gcd(a,m)=1$ 时，原式变为求解 $ax+my=1$ ，两边同时对 $m$ 取模，得到 $ax\equiv1 (mod\ m)$ ，故 $x$ 模 $m$ 的正余数就是 $a$ 的乘法逆元

方法一需要快速幂(已经倒背如流了)，所以详细介绍扩展欧几里得算法：

扩展欧几里得算法是对欧几里得算法(辗转相除法)的扩展：

欧几里得算法核心： $gcd(a,b)=gcd(b,a\%b)$ ，那么辗转下去，直到 $b=0$ ， $gcd(a,0)=a$
扩展欧几里得的目标：在求 $gcd(a,b)$ 的同时，找到一组整数解 $x,y$ 满足 $ax+by=gcd(x,y)$ (这个方程一定有解)

使用数学归纳法推导递归过程中解的传递关系：

递归的终止条件为 $b=0$ ，那么方程为 $ax+0\cdot y = gcd(a,0)=a$ ，此时的一组解为 $(x,y)=(1,0)$

所以：

if(!b){
    x = 1;
    y = 0;
    return a;
}

当 $b\ne0$ ，即中间递归过程：

这一层为 $ax+by=gcd(a,b)$

$gcd(a,b)=gcd(b,a\%b)$

下一层为 $bx^{'}+(a\%b)y^{'}=gcd(b,a\%b)$

因为 $a\%b=a-\lfloor\frac{a}{b}\rfloor\times b$ ，所以变为 $bx^{'} +(a-\lfloor\frac{a}{b}\rfloor\times b)y^{'}=gcd(b,a\%b)$ ，即 $ay^{'}+b(x^{'}-\lfloor\frac{a}{b}\rfloor\times y^{'})=gcd(b,a\%b)$ 。

所以有 $x=y^{'},y=x^{'}-\lfloor\frac{a}{b}\rfloor\cdot y^{'}$

int g = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return g;

这里有些绕晕，更直观的代码：

int x1, y1;
int g = gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;

所以扩展欧几里得算法的模板为：

int exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    int g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}

求解逆元总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


int exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    int g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}
signed main(){
    HelloWorld;
    
    int q; cin >> q;
    while(q --){
        int a, m; cin >> a >> m;    
        int x, y; 
        int g = exgcd(a, m, x, y);
        cout << (x + m) % m << endl;
    }
    return 0;
}