数论：逆元
mydcwfy
·
·
个人记录
1. 定义
然后我们在处理 $d/a\pmod b$，可以转化为 $d*a^{-1}\pmod p$。
## 2. 求法
### 1） 扩展欧几里得算法
可以转化为 $a*x+b*y=1$，直接扩展欧几里得即可。
值得注意的是，我们要将 $x$ 变成 $[0,p-1]$ 的数。
```cpp
typedef long long ll;
ll ExGCD(ll a,ll b,ll &x,ll &y){
ll d;
if(b==0) x=1,y=0,d=a;
else
{
d=ExGCD(b,a%b,y,x),y-=a/b*x;
}
return d;
}
ll inv(ll a,ll p)// 求逆元的函数
{
ll x,y;
ExGCD(a,p,x,y);
x=(x%p+p)%p;
return x;
}
```
### 2）线性算法
首先，$1^{-1}=1$。
$[\dfrac{p}{i}]*i+r=p\Leftrightarrow [\dfrac{p}{i}]*i+r=0\pmod p$。
同时乘以 $i^{-1}*r^{-1}$，就可以得到 $[\dfrac{p}{i}]*r^{-1}+i^{-1}=0\pmod p$。
于是，$i^{-1}=-[\dfrac{p}{i}]*r^{-1}\pmod p$。
当然，这个也可以计算单个的逆元。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e6+10;
long long inv[N];
int main()
{
int n,p;
cin>>n>>p;
inv[1]=1;
for (int i=2;i<=n;++i) inv[i]=(p-(p/i))*inv[p%i]%p;
for (int i=1;i<=n;++i) printf("%d\n",(inv[i]%p+p)%p);
return 0;
}
```
### 3）快速幂
因为有费马小定理：$a^{p-1}=1\pmod p$，其中 p 为质数。
所以 $a*a^{p-2}=1\pmod p$。