线性时间递推 $0\sim p-1$ 在模 $p$ 意义下的乘法逆元。

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

设 $p=k\ast i+r\left(1\le r \lt i\lt p\right)$。

所以有 $k\ast i+r\equiv 0\pmod p$。

两边同乘以 $r^{-1}$、$i^{-1}$，有 $i^{-1}\equiv -k\ast r^{-1}\pmod p$。

即 $i^{-1}\equiv -\lfloor \frac pi\rfloor\ast (p\pmod i)^{-1}\pmod p$

洛谷p3811

const int MAXP=3e6+5;
int inv[MAXP];
void get_inv(int p){
	inv[1]=1;
	_for(i,2,p)
	inv[i]=1LL*(p-p/i)*inv[p%i]%p;
}