递推求逆元

问题

对于一个奇素数 p1\ ..\ p-1 中所有数的逆元。

公式

在这里把 n 的逆元表示成 Inv[n] 则有

Inv[n]\ = \ (p\ -\ p\ /\ n)\ *\ Inv[p\ \%\ n]\ \%\ p

其中显然有Inv[1]\ =\ 1这同时也是递推的边界。

证明

不防令 t\ =\ p\ /\ n k\ =\ p\ \%\ nnt\ +\ k\ =\ p
那么则有 nt\ +\ k\ \equiv\ 0\ (Mod\ p)
移项得 nt\ \equiv\ -k\ (Mod\ p)
两边同除以 nk-t\ *\ k^{-1}\ \equiv\ n^{-1}\ (Mod\ p)
也就是说 -t\ *\ Inv[k]\ \equiv\ Inv[n]\ (Mod\ p)

Inv[n]\ = \ (p\ -\ t)\ *\ Inv[k]\ \%\ p


带入得

Inv[n]\ = \ (p\ -\ p\ /\ n)\ *\ Inv[p\ \%\ n]\ \%\ p

代码

 

其他

求逆元的方法很多,这种方法的时间空间复杂度都是 O(n) ,非常适合那种需要初始化逆元的场合下使用。当 n 过大时,还是得使用费马小定理,扩展欧几里得这种方法去求。

完结

2 thoughts on “递推求逆元

  1. Pingback: 伯努利数求自然数幂和 | 火药

  2. Pingback: [bzoj2186] [SDOI2008] 沙拉公主的困惑 | 火药

发表评论

电子邮件地址不会被公开。 必填项已用*标注