基于 Farey 序列的 O(1) 在线模逆元，离散对数，模幂，二次剩余
bsdsdb
·
·
算法·理论
https://maspypy.com/o1-mod-inv-mod-pow
记 x\equiv y\pmod P 为 x\equiv y(P)。
Farey 序列
记 F_n 为 n 阶 Farey 序列，就是所有分母不超过 n 的既约真分数带上 \frac01 和 \frac11 排序组成的序列，如 F_5=[\frac01,\frac15,\frac14,\frac13,\frac25,\frac12,\frac35,\frac23,\frac34,\frac45,\frac11]。
::::info[引理]
对任意 v\in[0,1],n\in\Z_{>0} 存在 \frac pq\in F_n 使得 |v-\frac pq|\le\frac1{qn}。符合的 \frac pq 一定是 \max(F_n\cap[0,v]) 或者 \min(F_n\cap[v,1])。
:::success[证]
第一部分，\{x\}\coloneqq x-\lfloor x\rfloor。将 \{\{iv\}:i\in[0,n],i\in\mathbb Z\} 排序，易得定存在 0\le i<j\le n 使得 |\{jv\}-\{iv\}|\le\frac1n。令 q\coloneqq j-i,p\coloneqq\lfloor jv\rfloor-\lfloor iv\rfloor。
|qv-p|=|\lfloor jv\rfloor+\{jv\}-\lfloor iv\rfloor-\{iv\}-p|\le\frac1n
第二部分，不妨设我们找到的 \frac pq<v。如果 (\frac pq,v) 之间还有 F_n 中的 \frac{p'}{q'}，那么 v-\frac pq>\frac{p'}{q'}-\frac pq\ge\frac1{qq'}\ge\frac1{qn} 从而矛盾。
:::
::::
下面三种算法，都是先找到 |\frac xP-\frac pq|\le\frac1{qn} 的 \frac pq，就有 |qx-pP|\le\frac Pn，t\coloneqq qx\bmod P\in[-\frac Pn,\frac Pn]。
怎么找 \frac pq 呢？因为 F_n 中数两两之差大于 \frac1{n^2}，故 \lfloor\frac{n^2p}{q}\rfloor 互不相同，把所有这些值存起来然后用 \lfloor\frac{n^2x}{P}\rfloor 找前驱后继即可。这需要 \Omicron(n^2) 的时间。
\Omicron(P^{\frac23})-\Omicron(1) 逆元
求 x^{-1}\bmod P，先将所有可能的 t 的 t^{-1} 预处理出来（离线 \Omicron(1) 逆元），然后 x^{-1}\equiv qt^{-1}(P)。
[示例代码](https://qoj.ac/submission/1825491)
## $\Omicron(\frac{P^{3/4}}{\log^{1/2}(P)})-\Omicron(1)$ 离散对数
令 $g$ 为 $P$ 的原根，$\log(x)$ 表示 $g$ 为底的离散对数，有 $\log(-1)=\frac{P-1}2$。首先要知道预处理出 $[1,m]$ 中所有数的对数的复杂度为
$$
\begin{cases}
\Omicron\left(\sqrt\frac{Pm}{\log m}\right),&m\le\sqrt P\\
\Omicron\left(\frac{P^{3/4}}{\log^{1/2}(P)}+m\right),&\text{otherwise}
\end{cases}
$$
::::info[]
$m\le\sqrt P$ 时，考虑先对所有范围内质数的离散对数求解。发现一般的 BSGS 的 $\log(x)$ 实际上是固定 $B$ 然后求解整数对 $(y,z)$ 使得
$$
y\le\frac PB\\
z<B\\
{(g^B)}^y\equiv xg^z(P)
$$
由于有 $\pi(m)$ 次查询，左边要 $\frac PB$ 次哈希表插入，右边要 $\pi(m)\cdot B$ 次哈希表查找，令 $B\coloneqq\sqrt{\frac P{\pi(m)}}$ 即可。
有了所有质数的对数之后，利用 $\log(pq)\equiv\log(p)+\log(q)(P-1)$ 即可线性筛得出 $m$ 以内所有数的离散对数。
$m\ge\sqrt P$ 时，先求出 $[1,\sqrt n]$ 以内的离散对数，然后求 $\log(x)$ 时，令 $P=:kx+r$ 则
$$
\log(x)\equiv\log(-r)-\log(k)\equiv\frac{P-1}2+\log(r)-\log(k)\pmod{P-1}
$$
递推即可。
::::
由于 $n^2\le P$，预处理 $[1,\frac Pn]$ 上的离散对数，那么 $[-\frac Pn,-1]$ 的也同时可以求出来。$\log(x)\equiv\log(\frac tq)\equiv\log(t)-\log(q)(P-1)$。于是复杂度为 $\Omicron(n^2+\frac{P^{3/4}}{\log^{1/2}(P)}+\frac Pn)-\Omicron(1)$，取 $n\sim P^{\frac13}$ 即为 $\Omicron(\frac{P^{3/4}}{\log^{1/2}(P)})-\Omicron(1)$。
## $\Omicron(\frac{P^{3/4}}{\log^{1/2}(P)})-\Omicron(1)$ 模幂
$a^b\equiv g^{b\log(a)}(P)$，再预处理 $g$ 的光速幂即可。
## $\Omicron(\frac{P^{3/4}}{\log^{1/2}(P)})-\Omicron(1)$ 二次剩余
设 $g$ 是 $P$ 的一个原根，现在求解方程 $x^2\equiv a\pmod P$。将 $a$ 表示为 $g^k\bmod P$。如果 $k$ 是偶数那么 $g^{\frac k2}\bmod P$ 是一个解。否则 $a$ 不是二次剩余。