主要参考：OI-WIKI

为什么要逆元

当一个题目让你求方案数时常要取余，虽然\((a+b)\% p=(a\% p+b\% p)\%p\)\((a-b)\% p=(a\% p-b\% p)\%p\)\((a\times b)\% p=(a\%p\times b\%p)\%p\)
但是\((\dfrac{a}{b})\%p\ne(\dfrac{a\%p}{b\%p})\%p\)
由于会出现这种情况，所以就要逆元了
一般情况下，当\(ax=1\)时，x 是 a 的倒数，\(x=\dfrac{1}{a}\)
毕竟是取余，所以当\(ax\equiv 1\pmod p\)时， x 叫做 a 关于 p 的逆元，用 \(a^{-1}\) 表示
于是 \((\dfrac{a}{b})\%p=(a\%p\times b^{-1}\%p)\%p\)
这样就把除法转换成乘法，解决了问题

如何求逆元

前提：\(\gcd(a,p)=1\) (本蒟蒻现在才发现模数这么奇怪原来有意图，如

)

费马小定理

\(\because a^p\equiv a\pmod p \\ \therefore a^{p-2}\equiv\dfrac{1}{a}\pmod p\)
证明：OI-WIKI(蒟蒻不会)
所以说\(a^{-1}\equiv a^{p-2}\pmod p\)
复杂\(O(\log p)\)

扩展欧几里得

\(ax+py=1\)的一组解 (x,y) ，x 是 a 关于 p 的逆元， y 是 p 关于 a 的逆元
证明：两边同时模 p\(\ \ \ \ \ \ \ \ \ \ \ ax+py=1\\ ax\%p+py\%p=1\%p\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ax\%p=1\%p\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ax\equiv 1\pmod p\)
所以 x 是 a 关于 p 的逆元，反之可以证明 y
复杂\(O(\log p)\)

连续的逆元

连续的逆元

如果直接暴力求，效率低，很有可能超时，如何线性(\(O(n)\))求呢？

首先 \(1^{-1}\equiv 1\pmod p\)
然后，设 \(p=k*i+r,r ，放到\(\pmod p\) 下就成了 \(k*i+r\equiv 0\pmod p\)
两边同时乘上\(i^{-1}\)和\(r^{-1}\)可得\(k*i*i^{-1}*r^{-1}+r*i^{-1}*r^{-1}\equiv 0\pmod p\)\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k*r^{-1}+i^{-1}\equiv 0 \pmod p\)\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i^{-1}\equiv -k*r^{-1}\pmod p\)\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i^{-1}\equiv -\lfloor\dfrac{i}{p}\rfloor*(p\mod i)^{-1} \pmod p\)
于是就可以从前面推出当前的逆元了，\(A[1]=1,A[i]=(p-p/i)*A[p\%i]\)
用 \(p-\lfloor\dfrac{p}{i}\rfloor\)防止出现负数，时间复杂度\(O(n)\)

阶乘的逆元

可以先处理 \(n!\) 的逆元，可以发现对于一个 \(1\le i，都有\(\dfrac{1}{i!}=\dfrac{1}{(i+1)!}*(i+1)\)
所以 \(i!\)的逆元\(A[i]=A[i+1]*(i+1)\%p\)，A[n] 先求出来，时间复杂度\(O(\log p+n)\)

求任意 n 个数的逆元

先算出前缀积 \(s_i\) 并预处理出 \(s_n\) 的逆元 \(sv_n\) ，
与阶乘的逆元相同，\(sv_i=sv_{i+1}*a_{i+1}\%p,1\le i 用这种抵消的方法可以\(O(n)\)处理出\(sv\)
求出了\(sv\)，\(a_i^{-1}\)可以用\(s_{i-1}*sv_i\)求得，时间复杂度\(O(\log p+n)\)