CF1806F GCD Master
Div. 2 的 2900，还是非常有难度的，看了题解才有思路。
这题是一个结论题，我们一步步来观察。不难发现每次操作相当于合并两个已经操作的集合，那么最终的问题就是把序列划分成了 \((n-k)\) 个集合。
- 结论一：考察最小值所在的集合 \(S_0\)，假设从小到大排好序的序列为 \(a\)，有
\[|S_0| > 1
\]
证明：考虑一个大小大于 \(1\) 的集合 \(S_1\)，若 \(S_0 = 1\)，则交换 \(S_1\) 中的最大值 \(x\) 和 \(a_1\)，带来的贡献为
\[\begin{align*}
&\gcd(S_1 \backslash \{x\} \cup \{a_1\}) + x - \gcd(S_1) - a_1 \\
\ge & \gcd(S_1 \backslash \{x\} \cup \{a_1\}) + x - (x - \min{S_1}) - a_1 \\
\ge & \gcd(S_1 \backslash \{x\} \cup \{a_1\}) + \min{S_1} - a_1 \\
\ge & 1
\end{align*}
\]
但是上面的推导基于 $\gcd{S_1} \le x - \min{S_1} $。 这当且仅当 \(S_1\) 中所有数不完全相同，所以有相同的数的情况留到最后单独讨论。
由于 \(\gcd\) 是不增的，有了第一个结论就不难发现推论：
- 结论二：仅有一个集合大小大于 \(1\)。证明比较显然。
这样就能做 F1 了。直接枚举 \(\gcd\) 就能做了。
但是到了 F2，不能枚举值域了，我们需要更加强大的结论。
- 结论三：最终的集合 \(S\) 可表示为 \(a\) 序列的一个前缀并上一个散点。
这个怎么证明呢？
假设选择的前缀为 \(p - 1\)，又另外选了两个数 \(x, y\)，那么
\[y - p \ge y - x \ge \gcd S
\]
所以
\[(\gcd S' + q) - (\gcd S + p) \ge \gcd S' \ge 1
\]
现在就可以做了，直接枚举前缀，注意到前缀 \(\gcd\) 只有 \(O(\log m)\) 种，所以分段计算贡献，直接算是 \(O(n \log^2 m)\) 的，但是散点与前缀的 \(\gcd\) 的总复杂度用势能分析可以做到 \(O(\log m)\)，这样就做到 \(O(n \log m)\) 了。
最后考虑有相同的数怎么做，很简单，只需要枚举做了多少次操作然后去掉一个前缀就行了。
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef __int128 i128;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
const i128 inf = (i128)1 << 126;
const int N = 1e6 + 10;
int n, k;
i128 g[N], a[N], c[N], m;
i128 d[N], b[N];
int l1, l2;
void solve() {
read(n), read(m), read(k);
i128 sum = 0;
for(int i = 1; i <= n; ++i)
read(c[i]), sum += c[i];
sort(c + 1, c + n + 1);
l1 = 0, l2 = 0;
for(int i = 1; i <= n; ++i)
if(c[i] == c[i - 1])
b[++l2] = c[i];
else a[++l1] = c[i];
i128 s = 0;
for(int i = 1; i <= l1; ++i)
g[i] = a[i];
for(int l = 1, r; l <= l1; l = r + 1) {
r = l;
g[r] = __gcd(a[r], g[r - 1]);
while(r < l1 && __gcd(g[l], g[r + 1]) == g[l])
g[++r] = __gcd(g[l], g[r]);
i128 mn = inf;
for(int j = r + 1; j <= l1; ++j) {
g[j] = __gcd(g[j], g[l]);
mn = min(a[j] - g[j], mn);
}
for(int j = l; j <= r; ++j)
s += a[j];
i128 t = s;
for(int j = r; j >= l; --j) {
d[j] = mn + t;
mn = min(mn, a[j] - g[l]);
t -= a[j];
}
}
for(int i = 1; i <= l2; ++i)
b[i] += b[i - 1];
i128 ans = 0;
for(int i = max(k - l1, 0); i <= l2; ++i)
ans = max(ans, sum - b[i] - d[k - i]);
write(ans); putchar('\n');
}
int main() {
int T; read(T);
while(T--) solve();
}