luogu题解 P3811 【【模板】乘法逆元】

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} ight floor,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} ight floor*{(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

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
");   //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
",inv[i]);
   }
   return ;
}
int main()
{
   read(n),read(p);
   inv[1]=1;
   make_inv();
   return 0;
}