自动搬运

查看原文

来自洛谷，原作者为

	dAniel_lele 当你在幻想上天会给你开一扇窗的时候，你已经输一半了。

搬运于2025-08-24 23:09:33，当前版本为作者最后更新于2025-01-04 23:54:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

$a$ 已经排好序了，先考虑求出 $T=\{1,2,\dots,x\}$，$S=\{x+1,x+2,\dots,n\}$ 的所有 $x$ 的答案。

考虑 $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))$，可以通过。