在线 O(1) 逆元

credit：zak 博客

AC link: qoj

考虑我们要求 $x$ 的逆元，但是 $x$ 可能很大，我们考虑找到一个数 $u$ 并且 $xu$ 比较小，那么我们就可以先预处理出 $xu$ 逆元再乘上 $u$ 得到 $x$ 的逆元。

令 $x=aB+c$，$B=p^{1/3},u\le \Theta(p^{1/3})$ 且 $|aBu| \le \Theta(p^{2/3})$。这样 $xu$ 就是 $\Theta(p^{2/3})$ 级别了。

考虑如何找到这样的 $u$。相当于我们需要找一个 $aBu \equiv v \in [-p^{2/3},p^{2/3}]$，也就是 $\frac{v}{u} \equiv aB \pmod p$，满足 $|v| \le p^{2/3}, u \le p^{1/3}$。

我们声称这样的 $(v,u)$ 肯定是能找到的，因为 $\{(v,u)\}$ 这一集合大小已经达到了 $2p$，其中 $\frac{v}{u}$ 必然有重复元素，取出一组 $(v,u),(v',u')$ 满足 $v\neq v', u < u'$ 即可组成一组合法的方案 $(v'-v,u'-u)$。这也是 黄忠庆功宴 一题的结论。

实现上，如何在合理的复杂度内找 $u$ 呢？我们先枚举 $u$，再遍历每一个合法的 $a$ 使得 $|aBu|$ 合法即可。由于 $Bu \ge p^{1/3}$，合法的 $a$ 只有 $p^{1/3}$ 个，再预处理 $p^{2/3}$ 个数的逆元，预处理复杂度 $O(p^{2/3})$，单组询问 $O(1)$，常数较小。