乘 法 逆 元
jijidawang
2020-04-01 21:39:29
前置芝士：
- 同余
## 普通逆元
逆元是模意义下的除法。
就是求解同余方程 $ax\equiv 1\pmod m$。
用 [exgcd](https://www.luogu.com.cn/blog/writeSTL/Exgcd) 求解即可。
Code:
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
void exgcd(int a,int b,int& x,int& y) //拓展欧几里得
{
if (!b){x=1;y=0;return ;}
exgcd(b,a%b);
int tmp=x;x=y;y=tmp-a/b*y;
}
int main()
{
int a,b,x,y;
scanf("%d %d",&a,&b);
exgcd(a,b,x,y);
printf("%d",(x+b)%b);//转 正
return 0;
}
```
---
## 素数的逆元
我们知道素数是有费马小定理的：
> 若 $p$ 为素数，则 $x^p\equiv x\pmod p$。
>
> 当且仅当 $x\nmid p$ 时：$x^{p-1}\equiv 1\pmod p$
然后我们用后面的式子同除以一个 $x$，可以得到 $x^{-1}\equiv x^{p-2}\pmod p$，所以我们只要求出 $x^{p-2}\bmod p$ 就可以了，用快速幂求解即可。
Code:
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll qpow(ll x,ll y,ll mod) //快速幂
{
ll ans=1,base=x;
while (y)
{
if (y&1) ans*=base;
base*=base;y>>=1;
}
return ans;
}
int main()
{
ll x,p;
scanf("%lld %lld",&x,&p);
printf("%lld",qpow(x,p-2,p));
return 0;
}
```
---
## 线性筛逆元
~~让人感受线性筛的奥妙~~
线性筛肯定是 $\mathcal O(n)$ 的嘛。
首先我们设 $p=ki+r$，然后可以知道 $ki+r\equiv 0\pmod p$（因为 $ki+r=p$，所以 $p\bmod \;p=0$）。
然后我们两边同乘 $r^{-1}i^{-1}$，就得到 $kr^{-1}+i^{-1}\equiv 0\pmod p$，移项得到 $i^{-1}\equiv -kr^{-1}\pmod p$。
我们可以知道 $k=\left\lfloor \dfrac{p}{i}\right\rfloor,r=p\bmod\;i$，所以我们得到公式：
$$i^{-1}\equiv -\left\lfloor \dfrac{p}{i}\right\rfloor\times p\bmod \;i^{-1}\pmod p$$
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
const int N=10001;
typedef long long ll;
ll inv[N];
void GetInv(ll n,ll p)
{
for (int i=2;i<=n;i++)
inv[i]=(-(p/i)*inv[p%i]%p+p)%p;
}
```
---
## 线性筛阶乘逆元
也就是线性筛 $n!^{-1}$。
我们设 $inv_i$ 表示 $i!$ 的逆元。
我们可以轻易知道 $inv_{i+1}=\left(\dfrac{1}{i+1}\right)!^{-1}$，我们同乘 $i+1$ 就变成了，$inv_{i+1}(i+1)=\left(\dfrac{1}{i!}\right)^{-1}=inv_i$，所以我们可以得到：
$$inv_{i+1}(i+1)=inv_i$$
所以我们先求出 $n!$ 的逆元，再倒推回来即可。
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll inv[3000100];
void GetFactInv()
{
inv[1]=inv[0]=1;
for (int i=1;i<=n;i++) //求阶乘
inv[i]=(inv[i-1]*i)%p;
inv[n]=GetInv(inv[n],p); //求n!的逆元
for (int i=n-1;i>=1;i--)//倒推
inv[i]=(inv[i+1]*(i+1))%p;
return 0;
}
```