费马小定理
适用范围：很广
\[a^{p-1}\equiv1\pmod p \quad p\in\mathbb{P} \]它可以看做是欧拉定理的特殊情况，欧拉定理为：
\[a^{\varphi(p)}\equiv 1\pmod p \quad (\gcd(a,p)=1) \]证明：
把与 \(p\) 互素的数放进一个集合 \(K=\{b_1,b_2,\dots,b_{\varphi(p)}\}\) 容易得出，它们都与 \(p\) 互素，且模 \(p\) 的值互不相等 （好像是句废话）
然后我们证明对于集合 \(K'=\{a\cdot b_1,a\cdot b_2,\dots,a\cdot b_{\varphi(p)}\}\) 里的元素也具有此性质，因为 \(a,b_i\) 分别与 \(p\) 互素，即同 \(p\) 没有除 \(1\) 外的公因子，所以 \(a\cdot b_i\) 也同 \(p\) 没有除 \(1\) 外的公因子，由此得出与 \(p\) 互素
通过反证法来证明 \(a\cdot b_i \bmod p\) 的值互不相等 ：
假设有一对 \(b\) 满足条件，设为 \(b_j,b_k\) 则 \(a\cdot b_j\equiv a\cdot b_k\pmod p\) 转化移项得： $ b_j\equiv b_k\pmod p$ 通过 \(b_i\) 之间的关系易得，假设不成立，故不存在一对 \(b\) 满足条件，即 \(K'\) 里的元素 \(\bmod p\) 互不相等，再加上互素的条件，可得 \(K'\) 在模 \(p\) 意义下与 \(K\) 等价
由此可以列出式子：
\[\begin{aligned} \prod\limits^{\varphi(p)}_{i=1} a\cdot b_i&\equiv\prod\limits^{\varphi(p)}_{i=1} b_i \\ \prod\limits^{\varphi(p)}_{i=1} a&\equiv 1\\ a^{\varphi(p)}&\equiv1\pmod p \end{aligned} \]\(Q.E.D.\)
正常情况下可以使用费马小定理求逆元，因为 \(a\cdot a^{p-2}\equiv 1\pmod p\) 所以模 \(p\) 意义下（p为素数） \(a^{-1}=a^{p-2}\) ，可以直接用快速幂求解，时间复杂度为 \(O(n)\)
线性递推逆元
柿子推导：
\[\begin{aligned} p &\equiv 0\pmod p\\ \left\lfloor p/i \right\rfloor\cdot i+p\bmod i&\equiv0\\ \left\lfloor p/i \right\rfloor\cdot (p\bmod i)^{-1}+i^{-1}&\equiv0\\ i^{-1}&\equiv-\left\lfloor p/i \right\rfloor\cdot (p\bmod i)^{-1}\\ i^{-1}&\equiv(p-\left\lfloor p/i \right\rfloor)\cdot (p\bmod i)^{-1} \end{aligned} \]阶乘递推求逆元
先求出 \(n!^{-1}\) 然后可以得出 $n!^{-1}\times n\equiv (n-1)!^{-1} \pmod p $ 然后线性递推即可
标签：cdot,bmod,varphi,pmod,逆元,互素,equiv From： https://www.cnblogs.com/Rolling-star/p/16537103.html