题解：P11694 [JRKSJ ExR] 淇宝的划分

· · 题解

首先有一个明显的贪心：

不难发现这个是错的，反例是：```3 5 6```，$T=\{3,6\},S=\{5\},ans=1$。 思考这个为什么是错的，好像没啥帮助。 这种问题看上去肯定是和我们最初那种贪心密切相关的，要不然的话也太难了。 绝对值很坏，我们拆开讨论一下。 令 $G=\gcd_{v\in S} v,L=\operatorname{lcm}_{v\in T} v$。 但在开始思考什么时候会选择不连续的 $T$ 之前，我们先考虑这样一个事情，如果取 $T={a_1}$，虽然很显然不对，但是会给我们提供一个优秀的答案上界。 ## $G>L

如果存在 a\in T,b\in S,a>b，则 L\ge a>b\ge G。

这个时候违反了限定条件，所以我们知道，T 一定是一个前缀，S 一定是一个后缀。

G<L

由于题目中同种元素会多次出现，这个很烦，我们尝试证明一下同种元素能否都分在同一个集合中：

假设 x\in S 且 x\in T。

也就是说 L-G 一定会变小，答案会更优。

那么也就是说，对于前缀 + 散块的情况，我们可以把元素进行去重处理。

对于去重完成的一个数组，该考虑数量的问题了。

假设我们有 s_2<s_1<\max_{v\in T}v=T_{\max}，我们有 G\le \gcd{(s_2,s_1)} = s_1-s_2。

那么 L-G\ge T_{\max}-(s_1-s_2) \ge s_1-(s_1-s_2)=s_2\ge a_1

回到开头的假设，我们会有 |a_1-\gcd_{v\in a_2\sim a_n }v| < a_1，所以这一定不优。

也就是说我们最多只会多余一个。

目前看来，似乎能做到 O(n^2) 了，可是还是无法通过，有什么性质没有被发掘呢？

我们不妨考虑这样一个事情，对于 j\in [1,i-1]，其中 a_1\sim a_i \in T,a_{i+1} \sim a_{n} \in S。我们要把 a_j 从 T 丢到 S 中。

哪一个是最优秀的哪一个呢？

考虑这样一个事情，如果 j+2<i，那么 a_{j+1} 和 a_{j+2} 都会出现在 T 中，则 L\ge \operatorname{lcm}(a_{j+1},a_{j+2}) \ge a_j+a_1，后面那个是简单的。

又因为 G\le a_j，所以会有：

L-G\ge \operatorname{lcm}(a_{j+1},a_{j+2})-a_j\ge a_1

这个东西和上面一样死掉了，也就是说，只有 j=i-1 的时候，才有可能会更优。

也就是说，我们只需要考虑额外的一个位置就好，也就是答案一定是以下两种形式之一：

时间复杂度被压缩到 O(n)，当然算上 \gcd 还是要带上 \log 的，问题不大。