逆元

啥是逆元？

若$a\times x\equiv 1\pmod{p}$且$\gcd(a,p)=1$，那么我们就定义$x$为$a$在模$p$下的逆元，记为$a^{-1}$。
所以，对于$\frac{a}{b}\pmod{p}$，我们先求助$b^{-1}$，再乘上$a$，再$\bmod p$，就是这个分数了。

给定$n$和$p$，求$n$在模$p$下的逆元。（$p$是质数）

这里可以用费马小定理求解。

众所周知$a^{\varphi(p)}\equiv 1\pmod{p}$，若$\gcd(a,p)=1$。

又众所周知若$p$是质数，$\varphi(p)=p-1$，上式变为$a^{p-1}\equiv 1\pmod{p}$。

则有（假设$p$是质数）：

$a\times x\equiv 1\pmod{p}$

$a\times x\equiv a^{p-1}\pmod{p}$

$a\times x\equiv a^{p-2}\pmod{p}$

这里的$a^{p-2}$就是$a$在模$p$下的逆元。

给定$n$和$p$，求$1$到$n$在模$p$下的逆元。（$p$是质数）

zcysky：逆元有线性递推的公式，推一下就好了呀。
首先有对于$\forall p\in Prime$，设$inv_n$为$n$在模$p$下的逆元，则$inv_1=1$。

则$inv_{i+1}=inv_{p\bmod i}\bmod p\times (p-\left\lfloor\dfrac{p}{i}\right\rfloor)$