本文介绍了一种 \(\Theta(p^{2/3})\) 预处理，\(\Theta(1)\) 询问逆元的方法。
首先，有 Dirichlet 逼近定理：
对于任意实数 \(\alpha\) 与给定的正整数 \(Q\)，存在整数 \(x,y\) 满足 \(1 \le y \le Q\) 且 \[ \left\lvert\alpha-\frac xy\right\rvert \le \frac1{y(Q+1)} \]
显然，若增加条件 \(\gcd(x,y)=1\)，该命题仍然成立。
证明：
我们用 \(\{\alpha\}=\alpha-\lfloor\alpha\rfloor\) 表示 \(\alpha\) 的小数部分。
令 \(I_n\) 表示区间 \(\left[\frac{n-1}{Q+1}, \frac n{Q+1}\right)\)，考虑 \(\{\alpha\}, \{2\alpha\}, \dots, \{Q\alpha\}\)。
如果其中有某个 \(\{y\alpha\} \in I_1\)，我们取 \(x = \lfloor y\alpha\rfloor\) 就有 \(0 \le y\alpha - x < \frac1{Q+1}\)；类似地，如果其中有某个 \(\{y\alpha\} \in I_{Q+1}\)，取 \(x = \lfloor y\alpha\rfloor+1\) 就有 \(-\frac1{Q+1} \le y\alpha - x < 0\)。
如果这两者都不成立，根据鸽巢原理，\(I_2, I_3, \dots, I_Q\) 中必有某个区间同时包含其中两个元素，从而存在 \(y_1 < y_2\) 使得 \(|\{y_1\alpha\}-\{y_2\alpha\}| \le \frac1{Q+1}\)，取 \(x = \lfloor y_2\alpha\rfloor-\lfloor y_1\alpha\rfloor, y = y_2 - y_1\) 即可。
从而定理对 \(\alpha > 0\) 成立。类似可知定理对所有 \(\alpha \in \mathbb R\) 成立。
于是，若询问 \(a^{-1} \bmod p\)，考虑选取适当的阈值 \(Q < p\)，找到一组 \(x,y\) 使得 \[ \left\lvert \frac ap - \frac xy \right\rvert \le \frac1{y(Q+1)} \iff \left\lvert ay - xp \right\rvert \le \frac p{Q+1} \]
这也就是说，存在 \(u = ay - xp\) 满足 \(ay \equiv u \pmod p\) 且 \(|u| \le \left\lfloor\frac p{Q+1}\right\rfloor\)。预处理 \(\left\lfloor\frac p{Q+1}\right\rfloor\) 以内的逆元即可 \(\Theta(1)\) 询问 \(a^{-1} \equiv u^{-1} y \pmod p\)。
而找 \(x,y\)，可以考虑求出 Farey 序列 \(F_{Q-1}\)（包含 \([0,1]\) 上所有分母小于 \(Q\) 的最简分数）。这可以暴力枚举，也可以用 Stern-Brocot 树的迭代构建。
考虑询问，自然只需要找 Farey 序列 \(F_{Q-1}\) 里 \(\frac ap\) 附近的两个分数即可。我们考虑一个映射 \(\frac xy \mapsto \left\lfloor\frac{x(Q+1)^2}{y}\right\rfloor\)。这自然是一个单射，且陪域是 \(\mathbb Z \cap \left[0, (Q+1)^2\right]\)，从而可以直接在陪域上预处理前驱后继来查询。
时间复杂度是 \(\Theta\left(Q^2 + \frac pQ\right)\)，取 \(Q = \Theta(p^{1/3})\) 即可达到 \(\Theta(p^{2/3})\) 预处理。
这里有我的一份实现，常数上自然还是不如离线做法的。