1. 什么是乘法逆元？
百度百科上是这样解释的：
乘法逆元，是指数学领域群 G 中任意一个元素 a ，都在 G 中有唯一的逆元 a'，具有性质 a×a'=a'×a=e，其中 e 为该群的单位元。
不用看了，我知道你看不懂
逆元其实很简单，
若 (acdot xequiv1 pmod {p})，（一般 (p) 为质数）
则称 (x) 为 (a) 对 (p) 的逆元，记为 (operatorname{inv}(x)=a)。
2. 乘法逆元能干嘛？
逆元一般用来求形如 (frac{a}{b} mod p) 的式子的值，
设 (k) 为 (b) 对 (p) 的逆元，则有 (frac{a}{b} mod p=akmod p) 。
下面来看看这个式子是怎么推导的。
设 (k) 为 (b) 对 (p) 的逆元，即 (bkmod p=1)，有：
3. 逆元怎么求？
(1) exgcd
还记得这个式子吗？(axequiv 1 pmod {p})，
这个式子可以转化为 (ax+py={1})，（(yinmathbb{Z})）
这个时候就可以用 exgcd 来求逆元，
时间复杂度大约为 (mathcal O(log n)) 。
#include<bits/stdc++.h>
using namespace std;
void exgcd(int &x,int &y,int a,int b)
{
if(!b)
{
x=1,y=0;
return;
}
exgcd(x,y,b,a%b);
int t=x;
x=y;
y=t-a/b*y;
}
int main()
{
int n,p;//求n关于p的逆元
scanf("%d %d",&n,&p);
int x=0,y=0;
exgcd(x,y,n,p);
printf("%d",(x%p+p)%p);
return 0;
}
(2) 费马小定理
费马小定理：若 (p) 为素数，(ainmathbb{Z^+})，且 (a)、(p) 互质，则有 (a^{p-1}equiv 1(mod{p}))。
这时发现上式和式子 (axequiv 1 pmod {p}) 的右边部分都为 (1)，
所以，(axequiv a^{p-1}pmod p)，
化简得 (xequiv a^{p-2} pmod p)。
如果 (a^{p-2}) 用快速幂计算，时间复杂度将和 exgcd 同级，为 (mathcal O(log n))。
code:
#include<bits/stdc++.h>
using namespace std;
int FastPow(int a,int n,int mod)
{
int base=a,ans=1;
while(n)
{
if(n&1) ans=(base*ans)%mod;
base=(base*base)%mod;
n>>=1;
}
return ans;
}
int main()
{
int n,p;//求n关于p的逆元
scanf("%d %d",&n,&p);
printf("%d",FastPow(n,p-2,p));
return 0;
}
(3) 逆元的线性递推式
此处参考 https://zhuanlan.zhihu.com/p/100587745?utm_source=qq。
例如洛谷P3811，要求求区间 ([1,n]) 的所有数的逆元，这个时候， exgcd 和费马小定理都显得有些“笨”。于是，就有了线性递推式。
假设我们现在想求 (a) 的逆元，为了方便之后的推导，我们将 (p) 表示成这样的形式： (p=aq+r)。
此处，(q=lfloor p/a floor,r=pmod a)。
容易看出，(aq+requiv 0pmod p)。
移项整理可得 (aequiv -rcdot operatorname{inv}(q)pmod p)。
两边同时取倒数，得出 (operatorname{inv}(a)equiv -qcdot operatorname{inv}(r)pmod p)。
再将 (q=lfloor p/a floor,r=pmod a) 代入，我们就得到了逆元的递推式 (operatorname{inv}(a)equiv -lfloor p/a floorcdot operatorname{inv}(pmod a)pmod p)。
我们发现，式子中的 (-lfloor p/a floor) 有可能是负数，所以我们给它加一个 (p)。
所以，最终的递推式为：
真正实现的时候，将 (equiv) 当作 (=) 即可。
然后就可以实现 (mathcal O(n)) 递推啦。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=10000010;
int n,p,inv[N];
int main()
{
scanf("%d%d",&n,&p);
inv[1]=1;
for(int i=2;i<=n;i++)
inv[i]=(p-p/i)*inv[p%i]%p;
printf("%d",inv[n]);
return 0;
}
4.参考资料
https://blog.csdn.net/yu121380/article/details/81188274
https://www.luogu.com.cn/blog/zjp-shadow/cheng-fa-ni-yuan