【算法基础 & 数学】快速幂求逆元（逆元、扩展欧几里得定理、小费马定理）

原文链接

为什么需要逆元

首先，在算法竞赛中，很多情况下会遇到数值很大的数据，这个时候，题目往往会让我们对某个数去摸，来控制数据范围。

在±*运算中，我们可以对每个数单独取模，然后再对运算之后的数取模。

但是除法比较特殊，例如：$(40÷5)mod10\ne ((40mod10)÷(5mod10)))mod10$

那我们可以将其转化为乘法，就相当于：除以一个数，就是乘以一个数的倒数

这个时候就要用到逆元

逆元的概念

1.单位元

在一个集合中，对于某种运算，如果对于任何的集合元素a和元素e运算，得到还是集合元素a本身，就称e为这个运算下的单位元

• 例如

在加法中：对任意实数a：$a+e=e+a=a$， 则e为单位元，$e=0$
在乘法中：对任意实数a：$a\times e=e\times a=a$， 则e为单位元，$e=1$
（每种运算都有自己的单位元）

2.逆元

在一个集合中，对于某种运算，如果任意两个元素的运算结果等于单位元，则称这两个元素互为逆元

• 例如

在加法中：对任意实数a：$a+-a=0$， 而0是加法的单位元，则-a为加法的逆元
在乘法中：对任意实数a：$a\times a^{-1}=1$，则$a^{-1}$为乘法的逆元

3.模乘的单位元

对于模$n$乘法，所有模$n$和$a$同余的数都可以表示成：
$$a(modn)=kn+a(k\in Z)$$
令单位元为$e(modn)$，将$a(modn)$和$e(modn)$进行模乘运算，得到：
$$\begin{array}{c}\begin{array}{rl}& a(modn)\times e(modn)\\ & =(k_{1}n+a)(k_{2}n+e)\\ & =(k_1{k}_2{n}^2+k_{1}en+k_{2}an+ae)\\ & =(k_1{k}_{2}n+k_{1}e+k_{2}a)n+ae\end{array}\end{array}$$

根据单位元定义，
$$a(modn)\times e(modn)=a(modn)$$

带入定义式：
$$(k_1{k}_{2}n+k_{1}e+k_{2}a)n+ae=kn+a$$

则
$$\{\begin{array}{l}k=k_1{k}_{2}n+k_{1}e+k_{2}a\\ e=1\end{array}$$

也就是说，模乘的单位元是1

4.模乘的逆元

模乘运算中，任意整数$a(modn)$的逆元表示为：
$$a^{-1}(modn)$$
根据定义，满足：
$$a{a}^{-1}\equiv 1(modn)$$

可以理解为$a$和$a^{-1}$在$n$的作用下发生了反应，变成了1

但是，不像加减法和乘除法每个数（乘除法除0以外）都有逆元

对于每个数$a$均有唯一的与之对应的乘法逆元$x$，使得$ax\equiv 1(modn)$
逆元存在的充要条件：$gcd(a,n)=1$（这个数和模数互质）

此时，在模$n$的意义下，一个数$a$如果有逆元$x$，那么除以$a$就相当于乘以$x$

开始求逆元

如何在给定$a$和$n$的前提下给出逆元？

先在这里附上欧几里得定理

1.扩展欧几里得定理

已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式$ax+by=gcd(a,b)$

扩展欧几里得常用来求形如方程：ax + by = c 的整数通解或者特解。

等式方程 ax+by = c 是不一定有整数解x、y的
但是已知：若$c$，则方程$ax+by=c$必定存在整数解，否则必定无解（其推导如下）。
对于最简单的情况： 对于不完全为0的非负整数$a,b,gcd(a,b)$ 表示$a,b$的最大公约数，必定存在整数对$x,y$满足$a\times x+b\times y==gcd(a,b)$。 我们一般根据欧几里算法与最大公约数的关系由最简单的情况来拓展推导方程的通解。

已知：a % gcd(a,b) == 0，b % gcd(a,b) == 0；若整数x、y为方程 ax + by = c 的一组解
则 ax % gcd(a,b) == 0，by % gcd(a,b) == 0
则 ax + by % gcd(a,b) == 0
即 c % gcd(a,b) == 0
因此 方程 ax + by = c 有解的充要条件是 c % gcd(a,b) == 0
————————————————
版权声明：本文为CSDN博主「阿阿阿安」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_40772692/article/details/81183174

• 下面举一个例子

【例题】给定正整数$a,b$，求满足等式$ax+by=1$的$x$的最小正整数解。如果不存在，返回-1。

首先找出$a,b$的最大公约数，令$g=gcd(a,b)$
则，原式可以转化为：
$$g(\frac{a}{g}x+\frac{b}{g}y)=1$$
如果$ab=1(a,b\in Z^{+})$，则$a=1,b=1$

所以$g=1$

所以，只需要考虑$a,b$互素的情况

下面给出扩展欧几里得定理的代码：

int extend_gcd(int a,int b,int &x,int & y)
{
   
	if(b == 0)
	{
   
		x = 1;
		y = 0;
		return a;
	}
	// x,y调换传给下一次递归等价于x1 = y2
	int t = extend_gcd(b,a%b,y,x);
	//等价y1 = x2 -(a/b) * y2
	y -= a / b * x;
	return t;
}

那上面这个跟逆元有什么联系呢？
来看这道题

【例题】给定正整数$p$和$a$，求满足$ax\equiv 1(modp)$的最小正整数$x$，如果不存在，返回-1

乍看上去跟上面一点关系都没有
将原式换成：
$$ax=kn+1(k\in Z)$$
移项后得到
$$ax-kn=1$$
由于k是个整数，不分正负，所以可以表示为
$$ax+kn=1$$
于是，可表示为
$$ax+by=1$$

ll inv(ll a, ll n){
   
    ll x, y;
    ExpGcd(a, n, x, y);
    x = (x % n + n) % n;
    return x;
}

2.费马小定理

$b$存在乘法逆元的充要条件是$b$与模数$m$互质。当模数$m$为质数时，$b^{m-1}\equiv 1(modm)$,$b^{m-2}$为b的逆元

【例题】给定素数$p$和正整数$a$，求满足$ax\equiv 1(modp)$的最小正整数$x$，如果不存在，返回-1

当$a$是$p$的倍数时，$ax\equiv 0(modp)$，所以一定不存在
当不是倍数（a和p互质），$a^{p-1}\equiv 1(modp)\Rightarrow a\times a^{p-2}\equiv 1(modp)$

此时$a^{p-2}$就是a的逆元

• 这道题就是求的$a^{p-2}$，考的费马定理和快速幂

题目描述：给定 $n$ 组 $a_i,p_i$，其中 $p_i$ 是质数，求 $a_i$ 模 $p_i$的乘法逆元，若逆元不存在则输出 impossible。

注意：请返回在 $0\sim p-1$ 之间的逆元。

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

LL qmi(int a, int b, int p){
   
    LL res = 1 % p;
    while(b){
   
        if(b & 1) res = res * a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}

int main(){
   
    int n, a, p;
    cin >> n;
    
    while(n--){
   
        cin >> a >> p;
        int res = qmi(a, p - 2, p);
        if(a % p) cout << res << endl;      //保证a不是p的倍数
        else cout << "impossible" << endl;
    }
    
    return 0;
}