Maximum GCD on Whiteboard

Fix some candidate answer $d$. We want to know whether we can make every remaining number divisible by $d$ after using at most $k$ erases.

The important part: split operations never combine different original numbers. So each starting value $a_i$ can be judged independently. If it can be transformed into only multiples of $d$, we keep it. If not, we erase it. Then $d$ is feasible iff at most $k$ values are bad.

When is one number good?

Call a value $x$ good for $d$ if, using only split operations, it can end as a collection where every number is divisible by $d$.

Obviously, if $d\mid x$, then $x$ is good: do nothing.

Now suppose $x$ is not divisible by $d$. When can a split help?

A split chooses

$$x_1\le x_2\le x_3, \qquad x_1+x_2+x_3=x,$$

then keeps $x_1$ and $x_3$ while discarding $x_2$.

If after this split both kept numbers are already multiples of $d$, the smallest possible kept multiple is $d$. The discarded middle must be at least the smaller kept value.

So if the kept numbers are $d$ and $2d$, the smallest possible total is

$$d+d+2d=4d.$$

If the kept numbers are $d$ and $d$, the total is forced to be

$$d+d+d=3d,$$

which is already divisible by $d$, so it does not help with non-multiples.

That gives the bad lower range:

Any non-multiple $x<4d$ is impossible to fix.

There is no room to split it into two useful kept multiples. And recursively splitting does not magically help: any smaller good non-multiple would need the same kind of first useful split, so this lower-bound argument blocks the whole chain.

Every $x\ge 4d$ is good

Now we show the other direction. Let

$$x=qd+r, \qquad 0\le r<d.$$

If $x\ge 4d$, then $q\ge 4$.

Split $x$ into

$$d,\quad d+r,\quad (q-2)d.$$

The sum is

$$d+(d+r)+(q-2)d=qd+r=x.$$

The order condition also holds:

$$d\le d+r\le (q-2)d.$$

For $q=4$, the right side is $2d$, and $d+r\le 2d-1$ if $r>0$; if $r=0$, it is even easier. For larger $q$, there is obviously enough room.

The split keeps the smallest and largest values, which are

$$d \quad\text{and}\quad (q-2)d.$$

Both are divisible by $d$. The annoying middle part $d+r$ gets thrown away. Nice. The operation is basically a very legal trash chute.

So the full characterization is:

$$x \text{ is good for } d \iff d\mid x \text{ or } x\ge 4d.$$

Counting bad values for a fixed $d$

A value is bad exactly when

$$x<4d \quad\text{and}\quad d\nmid x.$$

Since all $a_i\le n$, we can keep a frequency array. For a fixed $d$, count all values below $4d$, then subtract the divisible ones below $4d$.

The positive multiples of $d$ that are strictly below $4d$ are only

$$d,\ 2d,\ 3d.$$

So:

$$\text{bad}(d)=\#\{a_i<4d\}-\text{freq}[d]-\text{freq}[2d]-\text{freq}[3d].$$

Use prefix sums over values to get $\#\{a_i<4d\}$ in $O(1)$:

$$\#\{a_i<4d\}=\text{pref}[\min(n,4d-1)].$$

Then $d$ is feasible iff

$$\text{bad}(d)\le k.$$

Scan $d$ from $n$ down to $1$, and the first feasible $d$ is the maximum possible beauty.

Complexity

For each test case:

• build frequencies: $O(n)$
• build prefix sums: $O(n)$
• scan all $d$: $O(n)$

Total over all test cases is

$$O\left(\sum n\right),$$

which is comfortably within limits.