本文介绍了一种 Θ(p2/3) 预处理，Θ(1) 询问逆元的方法。
首先，有 Dirichlet 逼近定理：
对于任意实数 α 与给定的正整数 Q，存在整数 x,y 满足 1≤y≤Q 且 |α−xy|≤1y(Q+1)
显然，若增加条件 gcd(x,y)=1，该命题仍然成立。
证明：
我们用 {α}=α−⌊α⌋ 表示 α 的小数部分。
令 In 表示区间 [n−1Q+1,nQ+1)，考虑 {α},{2α},…,{Qα}。
如果其中有某个 {yα}∈I1，我们取 x=⌊yα⌋ 就有 0≤yα−x<1Q+1；类似地，如果其中有某个 {yα}∈IQ+1，取 x=⌊yα⌋+1 就有 −1Q+1≤yα−x<0。
如果这两者都不成立，根据鸽巢原理，I2,I3,…,IQ 中必有某个区间同时包含其中两个元素，从而存在 y1<y2 使得 |{y1α}−{y2α}|≤1Q+1，取 x=⌊y2α⌋−⌊y1α⌋,y=y2−y1 即可。
从而定理对 α>0 成立。类似可知定理对所有 α∈R 成立。
于是，若询问 a−1modp，考虑选取适当的阈值 Q<p，找到一组 x,y 使得 |ap−xy|≤1y(Q+1)⟺|ay−xp|≤pQ+1
这也就是说，存在 u=ay−xp 满足 ay≡u(modp) 且 |u|≤⌊pQ+1⌋。预处理 ⌊pQ+1⌋ 以内的逆元即可 Θ(1) 询问 a−1≡u−1y(modp)。
而找 x,y，可以考虑求出 Farey 序列 FQ−1（包含 [0,1] 上所有分母小于 Q 的最简分数）。这可以暴力枚举，也可以用 Stern-Brocot 树的迭代构建。
考虑询问，自然只需要找 Farey 序列 FQ−1 里 ap 附近的两个分数即可。我们考虑一个映射 xy↦⌊x(Q+1)2y⌋。这自然是一个单射，且陪域是 Z∩[0,(Q+1)2]，从而可以直接在陪域上预处理前驱后继来查询。
时间复杂度是 Θ(Q2+pQ)，取 Q=Θ(p1/3) 即可达到 Θ(p2/3) 预处理。
这里有我的一份实现，常数上自然还是不如离线做法的。