警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「数学」离线乘法逆元科技

简介

一种非常简单的 \(O(n+\log p)\) 预处理任意 \(n\) 个数模 \(p\) 逆元的科技。

然后我就这样水了一篇 Blog?

传送门:洛谷 P5431 - 乘法逆元2LOJ #161. 乘法逆元 2

解法

令这 \(n\) 个数为 \(a_1, \cdots, a_n\)。那么显然有 \(\frac1{a_i} = \prod_{j\ne i}a_j\frac1{\prod_ja_j}\)

\(a_1a_2\cdots a_{i-1}a_{i+1}\cdots a_{n}\cdot\frac1{a_1a_2\cdots a_n}\)

那么只需要预处理前缀积和后缀积,然后算出 \(a_1a_2\cdots a_n\)(相乘)的逆元即可。

代码