给你一个p，要你求出1~p-1所有数在模p下的逆元。
一个一个用扩展欧几里得求？如果p特别大，不就超时了？我们想要在线性的时间复杂度内求出逆元。
这种方法只能在p为质数的情况下使用。
首先有$1^{-1}equiv 1(mod p)$
设$p=iq+r(0<r<p)$，在模p意义下得$iq+requiv 0(mod p)$。
两边同时乘$i^{-1}$和$r^{-1}$得：$$qr^{-1}+i^{-1}equiv 0(mod p)$$
$$i^{-1}equiv -qr^{-1}(mod p)$$
$$i^{-1}equiv -lfloor frac{p}{i} floor (p mod i)^{-1}(mod p)$$
$$i^{-1}equiv (p-lfloor frac{p}{i} floor)(p mod i)^{-1}(mod p)$$
所以我们只要线性推一下即可。时间复杂度$ heta(n)$
所以代码如下：
inv[1]=1; for(int i=2;i<p;++i) inv[i]=(p-p/i)*inv[p%i]%p;