题解 P3811 【【模板】乘法逆元】
Rising_Date
2018-08-18 18:03:22
## 逆元：
一般用于求 $\frac{a}{b}\ \;mod\; p$
## 定义：
若 $a*x ≡ 1 \;(mod \;p)$ ，且 $a$ 与 $p$ 互质，那么我们就能定义: $x$ 为 $a$ 的逆元，记为 $a^{-1}$ ，所以我们也可以称 $x$ 为 $a$ 的倒数( $mod \;p$ 意义下)。
所以对于 $\frac{a}{b}\ \; mod\;p$ ，我们就可以求出 $b$ 在 $mod\; p$ 意义下的逆元，然后乘上 $a$ ，再 $mod \; p$ ，就是这个乘法逆元的值了。
## 求法：
### First：费马小定理
定理内容：如果 $a,p$ 互质，那么 $a^{p-1} ≡ 1 \;(mod\; p)$
结合逆元方程 $a*x ≡ 1 \;(mod\; p)$ ,得到 $a*x ≡ a^{p-1}\;(mod \;p)$
$\;\;\;\;\;\;$根据同余的性质,若 $p$ 为质数,得到 $x ≡ a^{p-2}\; {mod \; p}$
$\;\;\;\;\;\;$即 $x = a^{p-2} \;mod\; p$, **快速幂** 求解即可
### Second：欧拉定理
定理内容：如果$a,p$互质，那么$a^φ(p) ≡ 1 \;(mod\; p)$，当 $p$ 为质数时，$φ(p)=p-1$。
同理，结合同余方程，得 $x=a^{p-2} \;mod \;p$, **快速幂** 求解即可
_（这只是两种不同的证明，代码是相同的）_
```cpp
//TLE_83分
#include<cstdio>
#define ll long long
using namespace std;
int n,p;
inline ll ksm(ll a,ll b){
ll ans=1;
a%=p;
while(b){
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans%p;
}
void write(ll x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);putchar(x%10^48);
}
int main(){
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++)
write(ksm(i,p-2)),putchar('\n');
return 0;
}
```
### Third:解不定方程
**解同余方程** $ax≡1 \;(mod \;p)$ 等价于 **解不定方程** $ax+py=1$
**Exgcd**求解即可（不会 请左转 [](https://www.cnblogs.com/RisingGods/p/9497928.html) _Exgcd_ ）
$\;\;\;\;\;\;$由于 $p$ 是质数，那么$gcd(a,p)=1$;
$\;\;\;\;\;\;$即求解不定方程 $ax+by=gcd(a,b)$;
```cpp
//AC_1240ms
#include<cstdio>
using namespace std;
int x,y;
void exgcd(int a,int b){
if(!b){x=1,y=0;return ;}
exgcd(b,a%b);
int t=x;
x=y,y=t-a/b*y;
}
void write(int x){
if(x>9) write(x/10);
putchar(x%10^48);
}
int main(){
int n,p;
scanf("%d%d",&n,&p);
for(int i=1;i<=n;++i)
exgcd(i,p),write((x%p+p)%p),putchar('\n');
return 0;
}
```
### Forth：线性递推
#### 复杂度 $O(n)$
#### 递推过程：
令 $p=ki+r$ ; {$\;k=\big\lfloor\frac pi\big\rfloor$, $r=p\;mod\;i\;$} $(i<p,k<p,r<i)$
$\;\;\;\;\;\;$则有 $ki+r≡0\;(mod\; p) $ ①
①式左右同乘$i^{-1}*r^{-1}$ 得：
$k*r^{-1}+i^{-1} ≡ 0 \;(mod \;p)$
移项 得
$\;\;\;\;\;\;$ $i^{-1} ≡ -k*r^{-1} \;(mod\; p)$
带入 $\;k=\big\lfloor\frac pi\big\rfloor$ , $r=p\; mod\; i$;
$\;\;\;\;\;\;$ $i^{-1}$ ≡ $\;-\big\lfloor\frac pi\big\rfloor$ $*(p\; mod \;i)^{-1} \;\;(mod\; p)$ ②
由于 $(p\; mod\; i) < i$ ,
$\;\;\;\;\;\;$ 所以,在求出 $i^{-1}$ 之前,我们早已求出 $(p\; mod \;i)^{-1}$；
$\;\;\;\;\;\;$ 因此用数组 $inv[i]$ 记录$i^{-1}$ ( $i$ 的逆元)
$\;\;\;\;\;\;$ 则$inv[i]=-\frac{p}{i}\ * inv[p\;mod\;i]\;mod\;p$ ;
不要以为到这里就结束了
$\;\;\;\;\;\;$ 因为我们需要保证 $i^{-1}>0$
$\;\;\;\;\;\;$ 所以,我们在②式右边$\;+p\; $( $p\;mod\; p=0$, 答案不变)
$\;\;\;\;\;\;$ 即 $inv[i]=p-\frac{p}{i}\ * inv[p\;mod\;i]\;\;mod\;p$;
$\;\;\;\;\;\;$ 当然 $inv[1]=1,inv[0]=tan90$°(赋值为$0$);
$\;\;\;\;\;\;$而且$for$循环 要从$2$开始，防止改变 $inv[1]$ 的值;
至此,证毕。
```cpp
//AC_664ms
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=3e6+5;
ll inv[maxn]={0,1};
int main(){
int n,p;
scanf("%d%d",&n,&p);
printf("1\n");
for(int i=2;i<=n;i++)
inv[i]=(ll)p-(p/i)*inv[p%i]%p,printf("%d\n",inv[i]);
return 0;
}
```