因为去年校赛遇到了,今年的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