不可根号 BSGS 时的若干解决办法

许多题如果用 \(O(\sqrt p)\) 的 \(\texttt{BSGS}\) 会超时，下面是我见过的若干解决办法。

前置知识：原根，离散对数，阶，BSGS。下文设原根为 \(g\)，\(\text{ord}_r(a)\) 表示 \(a\) 模 \(r\) 的阶。

科技

重新平衡复杂度

可以 \(O(B+\frac{np}{B})\) 求出 \(n\) 个数的离散对数，只是把原来的根号重新平衡了一下。具体来说：预处理 \(g^0,g^1,\dots,g^{B-1}\)，记录到 map 上。查询时判断 \(x\times g^{kB}\) 在 map 上的值即可。应用：P9994。

单次 \(\log\) 但预处理较慢

可以 \(O(\dfrac{p^{3/4}}{\log p})\) 预处理，\(O(\log p)\) 查询一个数的离散对数。这里 Ctrl+F：BSGS 即可。

简单粗暴地应用：\(\forall 1\le i\le n\)，求 \(i^i\) 对 \(10^9+7\) 取模，\(1\le n\le 2\times 10^7\)。更优秀地方法。

取原根，转化为求 \(1\sim n\) 的离散对数，最后光速幂一下即可。

由于 \(\log(ab)=\log a+\log b\)，于是只要求素数处的离散对数，套用上述方法即可。复杂度 \(O(\dfrac{n\log p}{\ln n}+\dfrac{p^{3/4}}{\log p})\)，可以看做线性。