乘法逆元
若\(ax \equiv 1(\bmod p)\),则\(a\)与\(x\)在模\(p\)意义下互为乘法逆元
记为\(a=inv[x],a^{-1}=x\)
使用场景
若出现\((\frac{a}{b})\bmod p\),不能等价于\(\frac{(a\bmod p)}{(b\bmod p)}\),此时可以用\(a\)乘以\(b\)的逆元\(inv[b]\),\(a\times inv[b]\bmod p\)
求解逆元
情况一：求单个整数的逆元
- 1.扩展欧几里得算法
\(ax\equiv 1(\bmod p)\Rightarrow ax+py=1\)
- 2.有限情况下使用费马小定理
情况二：求\(1\)到\(n\)的所有整数模\(p\)意义下的逆元（前提是存在） - 1.线性求逆元
ps:
- 1.乘法逆元不一定存在
- 2.乘法逆元若存在，那么有无数个，但在模\(p\)意义下只有1个
费马小定理
若\(p\)是质数，且\(gcd(a,p)==1\),那么\(a^{p-1}(\bmod p)\)
由此可知：\(a^{p-2}\times a \equiv 1(\bmod p)\)，即\(x=a^{p-2}\)
线性求逆元
设\(p=a\times q+r\),其中\(q=p/a,r=p%a\)
则\(p=a\times q+r \equiv 0(\bmod p)\)
\(a \equiv -r\times inv_q(\bmod p)\)
\(inv_a=-q\times inv_{p\bmod a}\)
\(\therefore inv_a=-\frac{p}{a}\times inv_{p\bmod a}\)
代码：
inv[1]=1;
for(int i=2;i<=n;i++) inv[i]=p-(p/i)*inv[p%i]%p;