2025-06-25 随笔

基于值域预处理的快速离散对数

考虑下面一个经典题：

P11175 【模板】基于值域预处理的快速离散对数：给定质数 $p$ 和它的一个原根 $g$，有 $q$ 次询问，每次询问给出一个整数 $x\in [1,P)$，查询 $\log_g x\pmod{p}$ 的值。$1\leq p\leq 10^9+7,1\leq q\leq 5\times 10^5$

如果采用朴素的 BSGS 算法，时间复杂度 $O(q\sqrt{p})$ 难以接受。

先来考虑一个问题，如何快速求出 $1\sim n$ 的全体离散对数呢（也就是随后要 $O(1)$ 查询）？

一个朴素的方法是计算全体 $g^0,g^1,\cdots,g^{p-2}$，但是这样子就需要 $O(p)$ 的时间，在大多数场合是不能接受的（主要是没有利用到 $n$ 的范围）。

根据对数的性质 $\log ab=\log a + \log b$（$\log$ 指以 $g$ 为底的离散对数，下同），可以得到离散对数是一个（完全）和性函数，那么可以在线性筛中计算，不过这需要计算每个质数的离散对数。根据素数定理 $\pi(n)\sim \frac{n}{\log n}$，每次用 BSGS 计算质数的离散对数，时间复杂度是 $O(\frac{n\sqrt{p}}{\log n})$ 的吗？其实不是的。

考虑到我们 BSGS 其实在做这样一件事情：

• 取一个阈值 $B$，计算 $g^0,g^1,\cdots,g^{B-1}$，并且插入到哈希表中。
• 对于每一次查询，依次枚举 $k$ 计算 $g^{-kB}$，然后在哈希表中尝试查找 $g^{-kB}x$，如果找到了也就是找到了答案。

由于 $g$ 固定，所以我们可以将第一步预处理，时间复杂度 $O(B)$，第二步单次时间复杂度 $\frac{p}{B}$，总时间复杂度是 $O(\frac{np}{B\log n})$。故整体时间复杂度为 $O(B+\frac{np}{B\log n})$。根据均值不等式取 $B=O\left(\sqrt{\frac{np}{\log n}}\right)$ 最优，时间复杂度为 $O\left(\sqrt{\frac{np}{\log n}}\right)$。在本题中 $n=p-1$，时间复杂度 $O\left(\frac{p}{\sqrt{\log n}}\right)$。不过仍然无法通过本题，但是由于本题不需要 $O(1)$ 查询，所以实际上不需要处理全体 $n=p-1$ 的质数的离散对数。

我们改为用刚刚提到的线性筛算法求出 $n=\lfloor\sqrt{p}\lfloor+1$ 的离散对数，那么如果查询的 $x\in[1, n]$，就可以 $O(1)$ 回答。

如果 $x>n$ 呢？考虑取 $p=ax+b$，也就是 $a=\lfloor\frac{p}{x}\rfloor,b=p\bmod x$，那么根据对数的性质，我们可以得到两个本质相同的等式：

$$\begin{aligned} &\log(x)=\log\left(\frac{p-b}{a}\right)=\log\left(\frac{-b}{a}\right)=\log(p-1)+\log(b)-\log(a)\\ &\log(x)=\log\left(\frac{p+x-b}{a+1}\right)=\log\left(\frac{x-b}{a+1}\right)=\log(x-b)-\log(a+1) \end{aligned}$$

其中 $\log(p-1)$ 可以提前计算一下。

由于 $x>n$，所以 $a+1\leq n$，故无论是 $\log a$ 还是 $\log a+1$ 我们都已经处理过了，可以 $O(1)$ 回答。

至于 $\log b$ 或 $\log(x-b)$，由于 $\min(b,x-b)\leq \frac{x}{2}$，所以可以递归下去处理，这样递归深度是 $O(\log x)=O(\log p)$ 的，可以接受。

故时间复杂度为：

$$O\left(\sqrt{\frac{p\sqrt{p}}{\log \sqrt{p}}}\right)+O(q\log p)=O\left(\frac{p^{3/4}}{\sqrt{\log p}}+q\log p\right)$$

可以通过本题，代码超好写。

这个东西有什么用呢，考虑这个问题：

$q$ 次询问，每次询问给出 $n$，计算：

$$\prod_{i=1}^{n} i^{\varphi(i)}\pmod{998244353}$$

$q\sim O(\sqrt{n}),1\leq n\leq 3\times 10^7$。

$\varphi$ 可以通过线性筛处理，但是如果花费 $O(n\log n)$ 的时间计算 $i^{\varphi(i)}$ 是无法接受的（瓶颈在快速幂）。

考虑到 $q,n$ 严重不平衡，我们可以降低预处理的时间复杂度，提高查询的时间复杂度，从而使得整体时间复杂度平衡。具体地，我们选定原根 $g=3$，然后计算全体 $i\log\varphi(i)$ 的前缀积，这个过程如果真的用上面的算法就很笨，可以用刚刚所谓朴素的 $O(\sqrt{\frac{np}{\log n}})\approx O(n)$ 算法，然后查询时只需要计算 $g^{\prod_{i=1}^{n} i\log \varphi(i)}$ 即可，由于 $\prod_{i=1}^{n} i\log \varphi(i)$ 已经预处理出来，所以时间复杂度单次 $O(\log p)$（快速幂）。

总时间复杂度 $O(n+\sqrt{\frac{np}{\log n}}+\sqrt{n}\log p)$，优于 $O(n\log n)$。

警报器

先来看一道题：

P7603 [THUPC 2021] 鬼街：有一个长度为 $n$ 的序列 $a$，初始时全为 $0$。有 $q$ 次操作，支持：

• 0 x y 对于所有的 $i\in\mathbb{P},i\mid x$，$a_i\gets a_i+y$。
• 1 x y 安装一个警报器，具体地当 $\sum_{i\in\mathbb{P},i\mid x} \Delta a_i\geq y$ 时该警报器报警（$\Delta a_i$ 表示现在的 $a_i$ 减去警报器安装时的 $a_i$）。

在每一次 $0$ 操作后，输出当前有哪些警报器开始报警。

$2\leq n,m\leq 10^5$，强制在线，时间限制 $10\text{s}$。

由于 $10^5$ 以内每个数最多有 $\omega=6$ 个质因子，于是我们可以先对所有数质因数分解。

暴力的话应该是在修改的时候检查每一个位置关联的警报器，查询是否被触发，这样的时间复杂度大概是 $O(m^2)$ 显然是不行的。你发现如果我们有一种方法能够快速确定一个警报器能够触发，那么就可能可以用高级数据结构来维护，不过你应该可以注意到这几乎是不可能的。

考虑如何判定一个警告器是否被触发，我们有一个必要不充分条件：

$$\sum_{i\in S} i\geq y\implies \max_{i\in S}i\geq \left\lceil\frac{y}{|S|}\right\rceil$$

这是鸽巢原理的直接推论，我们先假装它是充分必要的，思考得到这个性质我们可以做什么。

一个非常直观的想法是对于每一个 $a_i$ 维护一个堆，然后对于每一个警报器，我们将警报器以 $\left\lceil\frac{y}{|S|}\right\rceil$ 为关键字插入到每一个关联的位置的堆中，修改时对于每一个修改的位置 $i$，我们可以弹出堆顶所有值小于等于当前 $a_i$ 的警报器，则这些警报器已经触发。

当然上述做法有一个致命的问题就是刚刚那个推论并不充分必要，因此会出现误判的情况，这个时候我们可以给它插回堆中，不过更新 $y$ 为新的变化量（减去了当前它关联的所有位置的变化量）。

欸你发现我们似乎一直在暴力啊，那这个新做法的时间复杂度是多少呢？由于每一次 miss 时我们总能令 $y$ 至少减去 $\left\lceil\frac{y}{|S|}\right\rceil$，所以实际上对于一个警报器，至多会 miss $O(\log_{\frac{\omega}{\omega-1}} V)$ 次，所以总时间复杂度是 $O(m\omega^2\log_{\frac{\omega}{\omega-1}} V\log m)$，可以通过本题。

这个 trick 被称为“折半警报器”，不过我们其实还有一个更快的方法，它是 zky 于今年 1 月份提出的“二进制警报器”，二进制警报器实现。