题解：CF2156C Maximum GCD on Whiteboard

· · 题解

这题就很数学了，很练思维。

首先当一个数是 g 的倍数时，它不需要做任何操作，这是显然的。

然后给出一些结论：

  1. 我们完全可以先删除数再分裂数，答案不会更劣。
  2. 设我们要使所有数都是 g 的倍数，对于一个数 x 它如果 \ge 4g，那它一定可以通过分裂来使得分成的两个数都是 g 的倍数。
  3. 如果 x < 4g，并且 x 不是 g 的倍数，那么 x 一定没有办法通过分裂来使得分成的两个数都是 g 的倍数，所以只能删除。

然后来证明：

  1. 采用反证法，假设有一个最优解，对于某个数 x，它将 x 分成了 x_1,x_2,x_3，然后删除了 x_1 或 x_3，那么我们完全可以先删掉 x，然后就不会有分裂操作，这样的话这个序列相当于少了一个数（x_1 或 x_2），对于这道题，少了一个数只可能更优或相等，但不会更劣。
  2. 我们完全可以将 x 拆成 (g,g+x \bmod g,x-2g-x \bmod g)，然后很显然满足 g \le g+x \bmod g \le x-2g-x \bmod g，并且 g 和 x-2g-x \bmod g 显然都是 g 的倍数。
  3. 使用数学归纳法，设 P_x 表示这个命题对于 x 的真假，那么 P_1 肯定成立，因为 1 无法分割，那么考虑 P_x，并且 \forall_{i(1 \le i \le x-1)} P_{i} = 1，当然 2 \le x < 4g,x \not\equiv 0 \pmod g，因为如果 x \ge 4g 或者 x \equiv 0 \pmod g，那 P_x 自然成立（前面已经证明），没意义。假设我们将 x 分成 x_1,x_2,x_3，并且 x_1+x_2+x_3 = x，那根据前面说的，P_{x_1} 和 P_{x_3} 都是无法分割使得分成的两个数都是 g 的倍数，所以想要证反，只有可能 x_1 和 x_3 都是 g 的倍数，如果 x_1 \ge 2g，则 x_3 \ge x_2 \ge x_1，那么 x = x_1+x_2+x_3 \ge 2g+2g+2g \ge 6g，显然和 x<4g 矛盾，因此，唯一的可能是 x_1 = g。假设 x_3 = g，那么根据 x_1 \le x_2 \le x_3 得出 x_1 = x_2 = x_3 = g，那么 x = 3g，与 x 不是 g 的倍数矛盾。最后就是 x_3>2g，于是 x = x_1+x_2+x_3 \ge g+g+2g = 4g，与 x<4g 矛盾。

证明完后， 你会发现，对于一个 g，它可行当且仅当：

[x \ge g]+[x = g]+[x = 2g]+[x = 3g] \ge n-k

然后你会发现可以用一个桶来记录每个数出现次数，那么就解决了第 2 \sim 4 个式子，然后第 1 个也就是加一个前缀和就行了。

所以说遍历 g = [1,n]，然后逐个判断是否可行即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int a[N];
int pre[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin >> _;
    while(_--)
    {
        int n,k;
        cin >> n >> k;
        for(int i = 1;i<=n;++i)
        {
            a[i] = 0;
        }
        for(int i = 1;i<=n;++i)
        {
            int x;
            cin >> x;
            ++a[x];
        }
        for(int i = 1;i<=n;++i)
        {
            pre[i] = pre[i-1]+a[i];
        }
        int ans;
        for(int i = 1;i<=n;++i)
        {
            if(n-pre[min(n,(i<<2)-1)]+a[i]+((i<<1)>n?0:a[i<<1])+(i*3>n?0:a[i*3])>=n-k)
            {
                ans = i;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}