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