线性求逆元

当要求 $1-n$ 中所有数的逆元时，$O(n\log p)$ 的方法就有点悬了。

下面介绍一种 $O(n)$ 求逆元的好方法。

推导

首先，$1^{-1}\equiv1\pmod p$。

设 $k=\lfloor\frac pi\rfloor$，则 $p=k\cdot i+r$，其中 $r=p\bmod i,1<i<p$。

易得 $k\cdot i+r\equiv0\pmod p$。

两边同乘 $i^{-1}\cdot r^{-1}$ 得：

$\begin{aligned} k\cdot r^{-1}+i^{-1}&\equiv0&\pmod p\\ i^{-1}&\equiv-k\cdot r^{-1}&\pmod p\\ i^{-1}&\equiv-\lfloor\frac pi\rfloor\cdot(p\bmod i)^{-1}&\pmod p \end{aligned}$

代码

for(int i=1;i<=N;++i) {
    inv[i]=-(mod/i)*inv[mod%i]%mod;
}

为使 $inv_i$ 非负，代码也可写成：

for(int i=1;i<=N;++i) {
    inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}