题解 P3811 【【模板】乘法逆元】
Rye_Catcher
2018-04-29 15:46:42
## upd--7.6 原线性求逆元代码数字一大会有锅
- 题目链接：
https://www.luogu.org/problemnew/show/P3811
- 概念：
一想到JXOI 2018考场上忘记逆元怎么打就觉得好笑，白白让T1落得如此下场.
推荐阅读：https://www.luogu.org/blog/zjp-shadow/cheng-fa-ni-yuan
我们可能经常遇到这样的情况(如JXOI2018 T1)
计算一个类似$a/b$%$p$的式子，根据同余性质我们是不能$a $%p$ /b $%p$ $这样计算的
但如果在普通算式中,显然$a/b$=$a*b^-1$。
在$\pmod p$中的意义下，我们不妨也构造一个$b^-1$，使得$b*b^-1 \equiv 1 \pmod{p}$;
那么$a/b \pmod p \equiv a*b^-1 \pmod p$，对于一开始的问题，我们可以放心地将$a$%$p$，然后乘上$b$在$\pmod p$意义下的逆元,太方便了
这就引出了逆元的定义：
_若$b*x \equiv 1 \pmod{p}$且$b,p$互质,则$x$为$b$在$\pmod p$意义下的逆元 ,记作$b^-1$_
- 思路：
算逆元一般有三种算法
- 拓展欧几里得
根据定义,若要求$b$在$\pmod p$意义下的逆元，就是求$b*x \equiv 1 \pmod{p}$中的x，转化成线性同余方程$b*x+p*y=1$,接着就用拓欧跑一遍就好
- 费马小定理
_若p是质数,则对于任意正整数b，有$b^{p} \equiv b \pmod{p}$_
所以$b^{p-1} \equiv 1 \pmod{p}$ 把b继续拆得到
$b*b^{p-2} \equiv 1 \pmod{p}$
对照上面逆元定义,我们只用求$b^{p-2} \pmod p$
- 线性递推
设$p=k*i+r$ 所以$k=\left \lfloor \frac{p}{i} \right \rfloor,r=p \mod i$
所以$k*i+r \equiv 0 \pmod p$ 同时乘以$i^-1,r^-1$
$k*r^-1+i^-1 \equiv 0 \pmod p$移项
$i^-1 \equiv -k*r^-1 \pmod p$
$i^-1 \equiv -\left \lfloor \frac{p}{i} \right \rfloor*{(p \mod i)}^-1\pmod p$
我们把所有的逆元存在inv[]数组里,那么
```
inv[i]=-((p/i)*inv[p%i]%p);
while(inv[i]<0)inv[i]+=p;
```
或者
```
inv[i]=(ll)(p-(p/i))*inv[p%i]%p;
```
当然inv[1]=1;
- 代码：
- 拓欧+费马小定理
```
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
LL mod(LL a,LL b)
{
if(a<b)return a;
if(a==b)return 0;
else return a-a/b*b;
}
LL pow_mod(LL a, LL b, LL p){//a的b次方求余p
LL ret = 1;
while(b){
if(b & 1) ret = mod((ret * a) ,p);
a =mod((a * a) ,p);
b >>= 1;
}
return ret;
}
LL Fermat(LL a, LL p){//费马求a关于b的逆元
return pow_mod(a, p-2, p);
}
void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d){
if (!b) {d = a, x = 1, y = 0;}
else{
ex_gcd(b, mod(a,b), y, x, d);
y -= x * (a / b);
}
}
LL inv(LL t, LL p){//如果不存在，返回-1
LL d, x, y;
ex_gcd(t, p, x, y, d);
return d == 1 ? (mod(x,p) + p) % p : -1;
}
int main()
{
int op;
LL a,p;
cin>>a>>p;
for(int i=1;i<=a;i++)cout<<inv(i,p)<<endl;
return 0;
}
```
- 线性递推
```
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
#deinfe ll long long
using namespace std;
const int maxn=3000005;
int n,p;
ll inv[maxn];
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
inline void make_inv(){
printf("1\n"); //inv[1];
for(register int i=2;i<=n;i++){
inv[i]=-((p/i)*inv[p%i]%p);
while(inv[i]<0)inv[i]+=p;
printf("%lld\n",inv[i]);
}
return ;
}
int main()
{
read(n),read(p);
inv[1]=1;
make_inv();
return 0;
}
```