数学笔记：逆元
逆元
一整数a对同余n之模逆元是满足以下公式的整数b
a^{-1} \equiv b \pmod{n}
也可以写成
ab \equiv 1 \pmod{n}
求逆元的方法
扩展欧几里得算法
费马小定理
费马小定理可以转换成如下形式
若a是一个整数，p是一个质数，则
a^{p-2} \equiv a^{-1} \pmod{p}
线性递推
我们设p=ki+r, r < i, 1 < i < p，然后把左边的式子展开
ki + r \equiv 0 \pmod{p}
两边同乘 (ir)^{-1}
\begin{aligned} kr^{-1} + i^{-1} &\equiv 0 &\pmod{p} \\ i^{-1} &\equiv -kr^{-1} &\pmod{p} \\ i^{-1} &\equiv -\lfloor \frac{p}{i} \rfloor \cdot (p \bmod i)^{-1} &\pmod{p} \end{aligned}
于是我们就得到了逆元的线性递推式：
inv[i] = -(MO / i) * inv[MO % i];
阶乘的逆元
先处理 (n!)^{-1} ，然后 [(n-1)!]^{-1} \equiv n(n!)^{-1} \pmod{p} 。
