乘法逆元 | 一个Oier

如果 ax ≡ 1 (mod p)，则称 x 为 a 在模 p 意义下的乘法逆元。

逆元存在当且仅当 a ⊥ p，即 gcd (a, p) = 1。

将 ax ≡ 1 (mod p) 转化可得，那么模意义下 t ÷ a 就相当于 t × x。

费马小定理

当且 p ∈ ℙ 时，有 a^p − 1 ≡ 1 (mod p)

由此转化可得 a × a^p − 2 ≡ 1 (mod p)，此时就可以发现 a^p − 2 即为 a 在模 p 意义下的乘法逆元。

此时可以用快速幂计算逆元，时间复杂度 O(log p)。

Exgcd 也可以用于求逆元。

由裴蜀定理可知，若 a ⊥ p，则必然，使得 a × x + p × y = 1 成立。

容易发现，a × x + p × y = 1 ⇔ a × x ≡ 1 (mod p)。

使用 exgcd 解出这个方程即可，时间复杂度 O(log p)。

现要求在 O(n) 的时间内，求出模 m 的意义下，[1, m) 中所有数的乘法逆元。

容易发现，∀ m ∈ ℤ，有 1 × 1 ≡ 1 (mod m)，所以 1 的逆元恒为 1。

考虑递推。

假设我们已知 [1, x) 内所有数的逆元，需要求出 x 的逆元。

将模数 m 表示为 kx + t，其中，t = m mod x。

由此可得 kx + t ≡ 0 (mod m)。

两边同乘 x⁻¹ × t⁻¹ (mod m)，可得 $$

$$ 即可得 x⁻¹ ≡ k × t⁻¹ (mod m)。

在此基础上代入，t = m mod x，可得由于 (m mod x)⁻¹ ∈ [1, x)，所以 (m mod x)⁻¹ 已知，线性递推即可。

PS 1：当 m mod x = 0 时 x 不存在模 m 意义下的乘法逆元。

PS 2：由于 C++ 中负数取模的结果为负数，所以在实际实现时递推式应写为 (m - m / x) * inv[m % x] % m。

综上所述，递推式即为：线性递推即可在 O(n) 的时间内完成。

显然，对于每一个数用快速幂 / exgcd 求解，时间复杂度为 O(nlog p)，无法通过本题。

考虑使用前缀积 {s_n}，其中 s_i 记录。

此外需要前缀积的逆元，使用 {t_n} 序列，其中 t_i = s_i⁻¹ (mod p)。

接下来可以通过快速幂 / exgcd 求解 s_n 的逆元，记为 t_n。

接下来可以通过如下公式线性递推求出 {t_n}：记原序列的逆元为 {inv_n}，其中 inv_i = a_i⁻¹ (mod p)。

由于已知前缀积数组的逆元，那么故递推即可，时间复杂度为 O(n + log p)，其中 O(log p) 是求 s_n 逆元的复杂度。