【学习笔记】逆元
NCC79601
2019-03-30 12:01:26
## 定义
求解除法取模运算时，令：
$$a\div b (\mod p)=a\times b^{-1}(\mod p)$$
其中：
$$b \times b^{-1}\equiv 1(\mod p)$$
## 正确性证明
$$\Rightarrow (a\div b) \mod p=(a\div b)\times 1\mod p$$
$$\because b\times b^{-1} \mod p=1,$$
$$\therefore \text{原式}=(a\div b)\times(b\times b^{-1})\mod p=(a\times b^{-1})\mod p$$
$$\Rightarrow (a\div b)\mod p=(a\times b^{-1})\mod p$$
## 定理
$a\div b\mod p=a\times b^{-1} \mod p$，其中$b^{-1}$为$b$的逆元。
## 逆元求法
### 费马小定理求法
首先要知道**费马小定理**：
如果$p$为**质数**，且$gcd(a,p)=1$，则：
$$a^{p-1}\equiv1(\mod p)$$
对这个式子进行变形：
$$a\times a^{p-2}\equiv1(\mod p)$$
所以当$gcd(a,p)=1$时，$a$关于$p$的逆元就是$a^{p-2}$。
继续推导，则：
$$a\div b \mod p=(a\mod p)\times (b^{-1}\mod p) \mod p$$
$$(\text{其中}b^{-1}=b^{p-2})$$
因此利用这种方法，逆元就可以用**快速幂**算出来。
### $\textbf{exgcd}$求法 $(p$为质数$)$
设$ax+py=gcd(a,p)=1$的解为$x$和$y$，那么$a$关于模$p$的逆元就是$(x\mod p+p) \mod p$。
---
代码
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int ExGcd(int a, int b, int &x, int &y) {
if(!b) {
x = 1, y = 0;
return a;
}
int gcd = ExGcd(b, a % b, y, x);
y -= a / b * x;
return gcd;
}
int main() {
int a, p, x, y;
scanf("%d%d", &a, &p);
ExGcd(a, p, x, y);
x = (x % p + p) % p;
printf("%d\n", x);
return 0;
}
```
### 线性递推求法
这个方法适用于求 [P3811](https://www.luogu.org/problemnew/show/P3811) 这种$[1,n]$范围内的逆元，复杂度为$O(n)$。
设$p=k* i+r$，其中$k=\biggl\lfloor\ \frac pi \biggr\rfloor=p/i,r=p\mod i$，则：
$$k* i+r\equiv 0(\mod p)$$
两边同乘$i^{-1}$和$r^{-1}$，得：
$$k* r^{-1}+i^{-1}\equiv 0(\mod p)$$
$$\Rightarrow i^{-1}\equiv -k* r^{-1}(\mod p)$$
把$k$和$r$的定义带入，即可得：
$$i^{-1}\equiv -(p/i)* (p\mod i)^{-1}$$
$$\Rightarrow i^{-1}=(p-p/i)* (p\mod i)^{-1}\mod p$$
$$\therefore \text{由}(p\mod i)\text{的逆元即可推知}i\text{的逆元}.$$
---
代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e6 + 10;
long long inv[MAXN];
int main() {
int n, p;
scanf("%d%d", &n, &p);
inv[1] = 1;
printf("1\n");
for(register int i = 2; i <= n; i++) {
inv[i] = (p - p / i) * inv[p % i] % p;
printf("%lli\n", inv[i]);
}
return 0;
}
```
---
还有一种简单的处理方法：
$$a/b\%c=(a\%(b*c))/b$$
---
**参考资料**
[除法逆元](https://www.cnblogs.com/zzqc/p/7192436.html)