【笔记】常见逆元计算方法总结
离散小波变换°
·
·
个人记录
方便起见，认为每次询问逆元的模数 P 均相同且为质数。
\mathcal O(\log P) 计算单个逆元
常用的方法有两种，一是利用费马小定理，而是利用 exgcd。
前者主要利用下式定理：
a^{P-1}\equiv 1 \pmod P \iff a^{P-2}\equiv a^{-1} \pmod P
只需要使用快速幂即可 \mathcal O(\log P) 计算。
后者将
\begin{aligned}
a\times a^{-1} &\equiv 1 &\pmod P \\
a\times a^{-1} &= kP+1 \\
a\times a^{-1}-kP&= 1
\end{aligned}
然后把 a, -P 视作已知数，a^{-1},k 视作未知数，带入经典的方程 ax+by=c 即可利用扩展欧几里得求解。
\mathcal O(n) 计算 1\sim n 逆元
假设已知 1\sim k-1 内每个数的逆元，尝试递推 k 的逆元：
\begin{aligned}
P&=vk+r \\
0&\equiv vk+r &\pmod P\\
k^{-1}&\equiv (-r)^{-1}\times v &\pmod P
\end{aligned}
然后注意到 (-r)^{-1}\equiv ((-1)\times r)^{P-2} \equiv (-1)^{P-2}\times r^{P-2}\equiv -r^{-1}，并且有 1\le r<k（因为 P 是质数，显然不存在 1<k<P 使得 k 整除 P），于是可以直接递推。
\mathcal O(n+\log P) 离线计算多个逆元
假设我们要对 x=[x_1, x_2, \cdots, x_n] 内每个数计算逆元。
考虑设 p_i = \prod_{k\le i} x_k，我们利用 \mathcal O(\log p) 的方法计算出 p_n 的逆元 p^{-1}_n，于是有：
\begin{aligned}
p_k^{-1} \equiv p_{k+1}^{-1} \times x_{k+1} & \pmod P \\
x_k^{-1} \equiv p_{k}^{-1} \times p_{k-1} & \pmod P
\end{aligned}
递推求解即可。
\mathcal O(n+P^{2/3}) 在线计算多个逆元
定理 1：
设 F_m 表示分子分母均不超过 m 的真分数再加上 0=0/1 和 1=1/1，经过排序去重后形成的序列（Farey 序列）。
对于任意实数 0\le \theta \le 1，我们在 F_m 里查询第一个大于等于 \theta 或者小于等于 \theta 的分数 x/y，那么这两者总是至少有一个满足 |\theta - x/y|\le 1/(my)。
（我太笨了不会证明，有空学习一下）
这个结论有什么用呢？考虑随便拿一个真分数 \dfrac{a}{b}，由定理存在分数 \dfrac{x}{y} 使得：
\begin{aligned}
\left|\frac{a}{b} - \frac{x}{y}\right| &\le \frac{1}{ny} \\
|ay-bx| & \le \left\lfloor\dfrac{b}{n}\right\rfloor
\end{aligned}
我们令 b=P，那么有 |ay-Px| \le \left\lfloor\dfrac{P}{n}\right\rfloor。在模 P 意义下，要么有 ay \bmod P\le \left\lfloor\dfrac{P}{n}\right\rfloor 要么有 P - (ay\bmod P)\le \left\lfloor\dfrac{P}{n}\right\rfloor，所以我们只需要预处理 1\sim \lfloor P/n\rfloor 内所有数字的逆元，接着只要查询这样的 y，即可快速回答 a 的逆元。
下面考虑怎么 n^2 计算 Farey 序列，以及如何查询这样的 x/y。
定理 2：
对于 F_m 里的分数 x/y，赋予其一个整数权值 \left\lfloor\dfrac{xm^2}{y}\right\rfloor 则两两不等，且可根据该权值进行比较。
证明：任取 F_m 当中两个不同的分数 \dfrac{x_1}{y_1} 和 \dfrac{x_2}{y_2}，不妨设前者小于后者，那么有：
\frac{x_2}{y_2} - \frac{x_1}{y_1} = \frac{x_2y_1-x_1y_2}{y_1y_2}
由于 y_1y_2\le m^2 且 1\le x_2y_1-x_1y_2，于是说明 \dfrac{x_2m^2}{y_2} - \dfrac{x_1m^2}{y_1} \ge 1，那么它们的权值必然不等。
并且由于 x\ge y，所以 0\le \dfrac{xm^2}{y}\le m^2。
于是只要枚举所有分子分母不超过 m 的真分数，按照权值进行桶排即可快速计算 Farey 序列；同时维护桶里每个数的前驱后继即可 \mathcal O(1) 查询。
预处理复杂度为 \mathcal O(m^2+P/m)，取 m=P^{1/3} 得到最优复杂度 \mathcal O(P^{2/3})；查询复杂度为单次 \mathcal O(1)。