[JRKSJ ExR] 淇宝的划分 题解

· · 题解

这里我们设 T 集合为所有在题面 T 中 a_i 的下标，S 同理。

考虑 $T=\{1\}$，$S=\{2,3,\dots,n\}$。我们可以得到 $\lvert(\gcd_{i\in S}a_i)-(\operatorname{lcm}_{i\in T}a_i)\rvert=\lvert(\gcd_{2\leq i\leq n}a_i)-a_1\rvert$。 分类讨论：按 $\gcd_{2\leq i\leq n}a_i$ 与 $a_1$ 大小关系分类。 等于的话答案必然是 $0$。 若 $\gcd_{2\leq i\leq n}a_i>a_1$，设 $v=\gcd_{2\leq i\leq n}a_i$，我们声称答案必然是 $0$ 或 $v-a_1$。如果 $T\neq\{1\}$，那么 $\operatorname{lcm}_{i\in T}a_i$ 必然是 $v$ 的倍数，而此时 $\gcd_{i\in S}a_i$ 要么是 $v$ 的倍数，要么比 $a_1$ 小。此时，两者的差要么等于 $0$，要么比 $v-a_1$ 大（此时一定不优），得证。注意到两者的差为 $0$ 必然有 $\max_{i\in T}a_i\leq\min_{i\in S}a_i$，所以我们已经讨论过的所有 $S,T$ 已经覆盖了此类情况。 接下来还剩 $\gcd_{2\leq i\leq n}a_i<a_1$ 的情况。也就是说，我们已经得到了一个答案小于 $a_i$ 的 $S,T$。考察所有存在 $i\in T,j\in S$ 使得 $a_i>a_j$ 的情况。 首先，我们声称，此时对于每一个 $x$，所有 $a_i=x$ 的 $i$ 将被放到同一个集合。 反证，不妨设对于某个 $x'$，有 $a_i=x'$ 被扔到 $S$ 里面了，也有被扔到 $T$ 里面了。 此时，要么存在 $i\in T$ 使得 $a_i>x'$，要么存在 $i\in S$ 使得 $a_i<x'$。 如果存在 $i\in T$ 使得 $a_i>x'$，考虑取出符合要求的一个 $i$。如果 $x'\mid a_i$，此时原式 $\geq a_i-x'\geq x'\geq a_1$，比我们已经得到的小于 $a_1$ 的解劣。如果 $x'\nmid a_i$，那么 $\operatorname{lcm}(x',a_i)\geq 2a_i$，原式 $\geq 2a_i-x'\geq a_i\geq a_1$，比我们已经得到的小于 $a_1$ 的解劣。 如果存在 $i\in S$ 使得 $a_i<x'$，考虑取出符合要求的一个 $i$。如果 $a_i\mid x'$，此时原式 $\geq x'-a_i\geq a_i\geq a_1$，比我们已经得到的小于 $a_1$ 的解劣。如果 $a_i\nmid x'$，此时原式 $\geq x'-\gcd(a_i,x')\geq x'-(x'-a_i)\geq a_i\geq a_1$，比我们已经得到的小于 $a_1$ 的解劣。 考虑将值相同的 $a_i$ 合并得到新的序列 $a$。此时，我们声称，选出的一定形如 $\texttt{TT}\dots\texttt{TSTSS}\dots\texttt{S}$，其中 $\texttt{T,S}$ 分别表示放入两集合。也就是说，至多有一个 $i\in S$ 小于 $\max_{j\in T}a_j$，至多有一个 $i\in T$ 大于 $\min_{j\in S}a_j$。 先证明至多有一个 $i\in S$ 小于 $\max_{j\in T}a_j$。同样考虑反证，不妨设有两个 $i_1>i_2$ 均符合要求。设 $\max_{j\in T}a_j=y$，此时原式 $\geq y-\gcd(a_{i_1},a_{i_2})\geq y-(a_{i_1}-a_{i_2})\geq a_{i_1}-(a_{i_1}-a_{i_2})\geq a_{i_2}\geq a_1$，比我们已经得到的小于 $a_1$ 的解劣。 然后证明至多有一个 $i\in T$ 大于 $\min_{j\in S}a_j$。还是反证，不妨设有两个 $i_1<i_2$ 均符合要求。设 $\min_{j\in S}a_j=z$，此时原式 $\geq\operatorname{lcm}(a_{i_1},a_{i_2})-z\geq 2a_{i_1}-z\geq 2z-z\geq z\geq a_1$，比我们已经得到的小于 $a_1$ 的解劣。 也就是说，我们只需要考虑形如： * $\texttt{TT}\dots\texttt{TSS}\dots\texttt{S}$； * $\texttt{TT}\dots\texttt{TSTSS}\dots\texttt{S}$。 两种情况即可。 预处理出前缀 $\operatorname{lcm}$ 与后缀 $\operatorname{gcd}$ 数组 $pre_i,suf_i$，可以 $O(n+\log V)$（或 $O(n+\log^2V)$）解决。第一种情况就可以 $O(n)$ 统计。（$\operatorname{lcm}$ 大于 $2\times10^{18}$ 的情况显然不优，此时我们统一按 $2\times10^{18}$ 计算） 容易分析得到对于所有有用的情况，$a_i\nmid pre_{i-2}$ 与 $suf_{i+2}\nmid a_i$ 的 $i$ 均为 $O(\log V)$ 的，于是，第二种情况也可以 $O(n+\log^2V)$ 统计。 总复杂度 $O(\sum(n+\log^2V))$，可以通过。