快速幂（二）

· · 个人记录

感谢 @云浅知处 的指导。

书接上文。测试题目。

如果说上一篇东西记录的是 O(p^\epsilon) 预处理 O(\log p) 查询离散对数，这篇东西记录的则是 O(\frac{p^{\frac34}}{\log^{\frac12}p}) 预处理 O(\log p) 查询离散对数。它的优势是什么？模数不需要被限制在 998244353 等素因子较小的数上。它的劣势是什么？慢，代码长，空间大（齐活！）。某些写法下，写测试题目可能会写得有点汗流浃背。

作为预处理，对 1 到 \sqrt{p}+1 的所有数求出离散对数。为了做到这一点，我们考虑提取其中所有 O(\frac{\sqrt p}{\log p}) 个素数求出离散对数后线性筛。采用 O(p^{\frac14}\log^{\frac12}p) 的块长可以把 BSGS 的总复杂度压到 O(\frac{p^{\frac34}}{\log^{\frac12}p})。注意这里我们不需要依赖哈希表，因为可以使用 p^\epsilon 为底数的基数排序。

作为查询，考虑如何求出 x 的离散对数。不难发现，如果 x\le\sqrt{p}+1，那么答案已经被预处理出来了。否则，记 p=vx+r，则 v\le\sqrt{p}（实际上取不到，但不重要）。我们考虑以下两个式子：

\log x=\log vx-\log v=\frac{p-1}2+\log r-\log v \log x=\log(v+1)x-\log(v+1)=\log(x-r)-\log(v+1)

不难发现 \log v 和 \log(v+1) 一定均已被预处理出，换而言之我们只需要知道 \log r 或 \log(x-r) 即可。而这两者必有其一小于 \frac x2，迭代下去即可，复杂度 O(\log p)。

以上。