本文介绍(O(n))处理([1, n])在模(P)意义下的逆元的方法。
结论
[inv_i equiv -lfloor frac{P}{i}
floor * inv_{(P mod i)} pmod P
]
证明
现在要求(i)的逆元：
设(a = lfloor frac{P}{i} floor， b = P mod i)，则
[a * i + b equiv 0 pmod P
]
[-a * i equiv b pmod P
]
等式两边同除(i * b)得
[-a * inv[b] = inv[i]
]
将(a = lfloor frac{P}{i} floor， b = P mod i)代入上式得
[inv_i equiv -lfloor frac{P}{i}
floor * inv_{(P mod i)} pmod P
]