题解 P3811 【【模板】乘法逆元】
Rising_Date
·
·
题解
逆元：
一般用于求 \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}
### 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求解即可（不会 请左转 Exgcd ）
$\;\;\;\;\;\;$即求解不定方程 $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)
①式左右同乘$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;
由于 $(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
$\;\;\;\;\;\;$ 即 $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;
}
```