「Luogu U71500 / EOJ 191C」星空夜 命题报告

题目大意

「Luogu U71500」星空夜

「EOJ 191C」最小公倍数 2

有 $n$ 颗星星，每颗可以用有序数对 $(a_i, b_i)$ 表示，意为它会在时刻 $a_i + k \times b_i (k \in N)$ 闪烁。给定 $q$ 组询问，每次指定一个区间 $[l, r]$，询问编号在这个区间中的星星是否可能在某时刻同时闪烁一次。

数据范围：$n, q \le 10^6, b_i \le 10^7$。

预计难度：提高组（？）。

我们令 $m$ 表示 $\max {r - l + 1}$，子任务如下：

• 对于 $25 \%$ 的数据，$q \le 10, m \le 10^3$。
• 对于 $50 \%$ 的数据，$q \le 10, b_i \le 10^6, m \le 10^5$。
• 对于另外 $10 \%$ 的数据，$n \le 10^3$。
• 对于另外 $20 \%$ 的数据，$l = 1$。
• 对于 $100 \%$ 的数据，无特殊限制。

其中 $50 \%$ 的数据满足 $b_i \le 10^3$，均匀分布在所有测试点中。

（不过这个题因为数据太难造最后投给 EOJ 了，就变成 ACM 题了，所以部分分仅供参考）

思路分析

算法一

首先进行初步的分析。不难发现可以将「星星会在时刻 $a_i + k \times b_i (k \in N)$ 闪烁」的条件替换成「星星会在时刻 $(a_i \bmod b_i) + k \times b_i (k \in N)$ 闪烁」，这不影响答案。这是因为如果在时刻 $x$ 选中的星星都会闪烁，那么在时刻 $x + \text{lcm}(b_1, b_2, \cdots, b_n)$ 它们也都会闪烁。这样，我们就可以预先把输入进来的 $a_i$ 全部对 $b_i$ 取模。

然后发现这个题目本质是询问一个区间的线性同余方程组是否有解。也就是询问：

$$\begin {cases} x \equiv a_1 \pmod {b_1} \\ x \equiv a_2 \pmod {b_2} \\ \cdots \\ x \equiv a_n \pmod {b_n} \end {cases}$$

是否有解。

注意到不能直接使用 ExCRT 的方法计算答案，因为答案可能很大。但是这题只需要我们判断方程组是否有解，所以无需算出答案。

可以证明：一个线性同余方程组有解当且仅当其中的任意两个方程形成的方程组都有解。原因是一个线性同余方程组的所有解一定可以写成满足「$x \equiv r_1 \pmod {p_1^{k_1}}, x \equiv r_2 \pmod {p_2^{k_2}}, \cdots$（$p$ 是素数）」这样一组的条件的任何数。如果一个方程组没有解，那么一定存在「$x \equiv r_1 \pmod {p_1^{k_1}}$，并且 $x \equiv r_2 \pmod {p_1^{k_1}}, $，其中 $r_1 \neq r_2$」这两个限制。而对于这两个限制，一定能找到两个方程，它们分别包含了两个限制的信息。也就是说，如果线性同余方程组无解，那么一定存在两个方程，它们组成的方程组无解。换句话说，如果任意两个方程形成的方程组都有解，则整个方程组一定有解。

我们暴力枚举每两个方程，判断它们是否矛盾即可。使用裴蜀定理即可证明它们不矛盾当且仅当 $\gcd(b_1, b_2)$ 整除 $a_1 - a_2$。时间复杂度 $O(n + qm^2 \log b_i)$。期望得分 $25$ 分。

算法二

考虑优化算法一。看到了 $\gcd$ 以后容易想到枚举因数。枚举因数 $d$，考虑所有 $b_i$ 是 $d$ 倍数的星星。如果所有 $a_i \bmod d$ 都相同的话，就没有矛盾。这样一次的复杂度是 $O(b_i \log b_i)$ 的，但是由于我们只需要枚举 $d$ 是素数或素数的几次方的情况，复杂度可以降为 $O(b_i \log \log b_i)$。

时间复杂度 $O(n + q(m + b_i \log \log b_i))$，期望得分 $50$ 分。

算法三

对于 $n$ 较小的情况，我们可以将是否矛盾的关系建成一个 01 矩阵，每次询问相当于问一个矩形是否全为 $0$。使用二维前缀和即可。时间复杂度 $O(n^2 \log b_i + q)$，结合以上算法期望得分 $60$ 分。

算法四

对于 $l = 1$ 的测试点，发现一定存在一点 $p$，使得 $r \le p$ 的答案为 Yes，$r > p$ 的答案为 No。在算法二基础上套个二分，计算出 $p$ 再回答询问即可。时间复杂度 $O((n + b_i \log \log b_i) \log n + q)$。

Nice Try. 期望得分 $10$ 分，结合上述算法期望得分 $70$ 分。

算法五

之前的算法好像没什么前途，考虑换一种思路。

对于每组限制 $(a_i, b_i)$，我们将 $b_i$ 素因数分解：$b_i = \prod_{j} p_j^{k_j}$ 。然后，对于每一个 $p_j^{k_j}$，将其拆成 $k_j$ 个限制，模数分别等于 $p_j, p_j^2, \cdots, p_j^{k_j}$，余数等于 $a_i$ 对它们取模的结果。对于一组 $(a_i, b_i)$，我们最多会将其拆成 $\log b_i$ 组限制。

拆分后的好处是什么呢？发现如果两个方程矛盾，那么从它们中一定可以各自选出一个限制，满足限制的模数相同，但余数不同。

这样我们就把问题转化成了：给定 $O(n \log n)$ 组有序数对 $(a_i, b_i)$，每次询问一个区间内是否存在 $b_i$ 相同且 $a_i$ 不同的一组数对。

对于 $l = 1$ 的数据，我们只需线性地扫一遍即可。用线性筛分解素因数，时间复杂度 $O(n \log b_i + b_i)$。期望得分 $20$ 分，结合上述算法期望得分 $80$ 分。

算法六

不难发现对于每一个点 $i$，一定存在一点 $p_i$ 使得以 $i$ 为右端点的区间 $[l, i]$ 中所有 $l \ge p_i$ 的答案都为 Yes，而 $l < p_i$ 的区间答案都为 No。考虑用 2 - pointers 预处理出 $p_i$。由于具体过程叙述起来较为复杂，请读者自行思考，也可以参考标程。

时间复杂度 $O(n \log b_i + b_i)$。期望得分 $100$ 分。

代码实现

#include <cstdio>