因为去年校赛遇到了，今年的Astar也遇到了，于是上网搜索了资料记下了这么简单的O(n)算法，科科。原理上一知半解，回头再好好理解理解吧。
这里求

1,2,...,p-1 mod p

的逆元，设

p = k*i + r (k = p/i, r = p%i)

即有

k*i + r ≡ 0 (mod p)

两边同时乘

(i^-1)*(r^-1)

得

k*(r^-1) + (i^-1) ≡ 0 (mod p)

即

(i^-1) ≡ -k*(r^-1) (mod p)

此时将

k = p/i, r = p%i

带入，得

(i^-1) = -(p/i)*((p%i)^-1)

若将x^-1化成数组NI[x]就是代码：

NI[i] = -(p/i)*NI[p%i];

还有就是可以简化到O(logp)得复杂度，但是那个我暂时还没想通，所以这里也不丢人0.0