前置知识：Farey 序列以及其相关理论，根号平衡。
这里稍微提一下什么是 Farey 序列 以及其性质：
* FnF_nFn 是第 nnn 阶的 Farey 序列，序列中存储所有不可约的分母 ≤n\le n≤n 的值在 [0,1][0,1][0,1] 之间的分数（这里认为 01,11\frac01,\frac1110 ,11 也是不可约的分数）按照其值从小到大排序得到的有序分数序列。
* 性质 111：对于 Fm−1F_{m-1}Fm−1 序列上任意两个相邻分数 ab,cd\frac ab,\frac cdba ,dc ，在 FmF_mFm 序列上一定按照顺序连续的存在分数 ab,a+cb+d,bd\frac ab,\frac{a+c}{b+d},\frac bdba ,b+da+c ,db 。
* 推论 111：对于 FmF_mFm 中任意两个相邻分数 ab,cd\frac ab,\frac cdba ,dc ，必然有 bc−ad=1bc-ad=1bc−ad=1。
* 性质 222：∣Fn∣=1+∑i=1nφ(i)|F_n|=1+\sum\limits_{i=1}^n\varphi(i)∣Fn ∣=1+i=1∑n φ(i)。
* 性质 333：对任意整数 n≥2n\ge 2n≥2 和任意实数 v∈[0,1]v\in[0,1]v∈[0,1]，一定可以在 Fn−1F_{n-1}Fn−1 序列中找到至少一个分数 xy\frac xyyx ，满足 ∣v−xy∣≤1yn|v-\frac xy|\le \frac1{yn}∣v−yx ∣≤yn1 。
* 推论 333：分数 xy\frac xyyx 一定是数 vvv 在序列 Fn−1F_{n-1}Fn−1 中向左查或者向右查能找到的第一个分数。
* 性质 444：对于 FnF_nFn 序列内的每个分数 xy\frac xyyx ，⌊xn22y⌋\lfloor\frac{xn^2}{2y}\rfloor⌊2yxn2 ⌋ 的值互不相同。
回到这个题目。考虑固定 nnn，记 v=apv=\frac apv=pa 。根据上面得到的性质和推论，可以知道此时必然存在一个分数 xy∈Fn−1\frac xy\in F_{n-1}yx ∈Fn−1 满足 ∣ap−xy∣≤1yn|\frac ap-\frac xy|\le\frac1{yn}∣pa −yx ∣≤yn1 。此时把不等式的左右两侧同时乘以 pypypy（显然有 py>0py>0py>0），得到：∣ay−px∣≤⌊pn⌋|ay-px|\le\lfloor\frac pn\rfloor∣ay−px∣≤⌊np ⌋。
记 u=ay−pxu=ay-pxu=ay−px，则此时又能得出两个结论：
* ay≡u(modp)ay\equiv u\pmod pay≡u(modp)
* ∣u∣≤⌊pn⌋|u|\le \lfloor\frac pn\rfloor∣u∣≤⌊np ⌋。
考虑把上面提到的结论 111 改写，得到：y≡u×a−1(modp)y\equiv u\times a^{-1}\pmod py≡u×a−1(modp)。因为这里想要求的是 aaa 在模 ppp 意义下的逆元即 a−1a^{-1}a−1，因此想到在同余式两侧同时乘以 u−1u^{-1}u−1，得到：a−1≡u−1×y(modp)a^{-1}\equiv u^{-1}\times y\pmod pa−1≡u−1×y(modp)。
然后再利用结论 222 即 ∣u∣≤⌊pn⌋|u|\le\lfloor\frac pn\rfloor∣u∣≤⌊np ⌋ 也就是 uuu 的绝对值很小，因此对这样的 aaa 只需在对应 Farey 序列上找出其对应的分数 xy\frac xyyx ，计算 u=ay−pxu=ay-pxu=ay−px，即可套用公式 a−1≡u−1y(modp)a^{-1}\equiv u^{-1}y\pmod pa−1≡u−1y(modp) 解决。而此时 u−1u^{-1}u−1 可以直接线性求逆元。
然而此时存在 u<0u<0u<0 的情况。对这个东西的处理是比较容易的，有 p−1≡−(−p)−1(modp)p^{-1}\equiv -(-p)^{-1}\pmod pp−1≡−(−p)−1(modp) 然后转化成上一种情况了。
问题在于怎么快速构造 nnn 阶 Farey 序列 FnF_nFn 。利用性质 222 可知 ∣Fn∣=1+∑i=1nφ(i)|F_n|=1+\sum\limits_{i=1}^n\varphi(i)∣Fn ∣=1+i=1∑n φ(i) 这个东西是 O(n2)O(n^2)O(n2) 量级的，而利用性质 444 可以想到开桶做到 O(V)=O(n2)O(V)=O(n^2)O(V)=O(n2) 排序，因此构造 FnF_nFn 的总时间复杂度为 O(n2)O(n^2)O(n2)。
而现在还需要找出 nnn 阶 Farey 序列上一个分数 xy\frac xyyx 的前驱 / 后继分数，容易想到直接在值域上维护前缀和，然后简单处理即可 O(n2)−O(1)O(n^2)-O(1)O(n2)−O(1) 查询。
因此总时间复杂度分为两个部分：
* 线性递推 ⌊pn⌋\lfloor\frac pn\rfloor⌊np ⌋ 以内数的逆元，时间复杂度为 O(⌊pn⌋)O(\lfloor\frac pn\rfloor)O(⌊np ⌋)。
* 求 nnn 阶 Farey 序列并在上面做一些处理，时间复杂度为 O(n2)O(n^2)O(n2)。
因此总时间复杂度为 O(n2+⌊pn⌋)O(n^2+\lfloor\frac pn\rfloor)O(n2+⌊np ⌋)，根号平衡一下就是 n2=⌊pn⌋n^2=\lfloor\frac pn\rfloorn2=⌊np ⌋ 解得 p=n13p=n^{\frac13}p=n31 ，此时时间复杂度为 O(p23+Q)O(p^{\frac23}+Q)O(p32 +Q)。
代码实现
参考文献
alfalfa_w 的文章 科技-在线 O(1)O(1)O(1) 逆元。
