菜王的 blog

首先单次查询离散对数可以考虑 BSGS，将 $g^0, g^B, g^{2B}, g^{3B}, \dots, g^{P / B \times B}$ 插入哈希表，然后枚举 $i = 0, 1, 2, \dots, B - 1$ 在哈希表中查询 $y \times g^{-i}$ 即可。

现在我们考虑求出 $\log 1, \log 2, \dots, \log n$ 怎么做。显然这个离散对数也满足 $\log ab = \log a + \log b$，所以我们只需要求出质数位置上的离散对数即可。

那么直接套用 BSGS 的做法，预处理时间复杂度为 $\mathcal{O}(P / B)$，所有查询时间复杂度为 $\mathcal{O}(\frac{nB}{\ln n})$，$P \ln n = n B^2$，平衡得到 $B = \sqrt{\frac{P \ln n}n}$。

考虑怎么预处理一些东西来快速回答询问。假设我们预处理了 $\sqrt P + 1$ 以内的 $\log$ 值，现在要求 $\log y$，那么若 $y \le \sqrt P + 1$ 就直接返回，否则令 $k, r$ 分别为 $P$ 除以 $y$ 的商和余数，考虑 $r$ 和 $y - r$ 之中一定有一个不大于 $y$ 的一半，如果能够规约到对应的子问题上，就可以做到单次查询 $\mathcal{O}(\log P)$。接下来有对应的两种方式：

1. 将模数 $P$ 表示为 $ky + r$，变形得到 $y = \frac{P - r}k = \frac{-r}k$，那么 $\log y = \log(-r) - \log k = \log(-1) + \log r - \log k$。
2. 将模数 $P$ 表示为 $(k + 1)y - (y - r)$，变形得到 $y = \frac{P + y - r}{k + 1} = \frac{y - r}{k + 1}$，那么 $\log y = \log(y - r) - \log(k + 1)$。

通过 $y > \sqrt P + 1$ 可以得出 $k \le \sqrt P$，那么 $\log k, \log (k + 1)$ 可以直接查表，选择对应的子问题递归下去即可。

回到前面预处理的部分，将 $n = \sqrt P$ 代入，得到 $B = P^{1/4} \ln^{1/2} P$。则预处理部分时间复杂度为 $\mathcal{O}\left(\frac{P^{3/4}}{\ln^{1/2} P}\right)$，可以通过。

代码