题解：CF2156C Maximum GCD on Whiteboard

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

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$ 矛盾。

#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;
}