Add 0 or K

The operation looks a bit annoying because every operation touches the whole array, but the key is that each element can independently choose whether it gets $+k$ or $+0$.

So after $m$ operations, element $a_i$ becomes

$$a_i + x_i k$$

where $x_i$ is the number of operations in which we chose to add $k$ to that element. Since $0 \le x_i \le m$, if we decide to use at most $k$ operations, then we are allowed to choose any

$$x_i \in \{0,1,2,\dots,k\}.$$

We do not need to output the operations, only the final array. So we just need to pick these $x_i$ values.

The trick

We want all final values to have gcd greater than $1$. The easiest way is to force all of them to be divisible by the same number.

Use the divisor:

$$k+1$$

Why? Because modulo $k+1$,

$$k \equiv -1 \pmod{k+1}.$$

So:

$$a_i + x_i k \equiv a_i - x_i \pmod{k+1}.$$

Now we want this to be $0$, so we need:

$$x_i \equiv a_i \pmod{k+1}.$$

The obvious choice is:

$$x_i = a_i \bmod (k+1).$$

And this is perfect because a remainder modulo $k+1$ is always between $0$ and $k$, exactly the range we can realize using at most $k$ operations. No awkward edge case hiding in the bushes.

Then the final value is:

$$a_i + k \cdot (a_i \bmod (k+1)).$$

Check divisibility:

$$a_i + k(a_i \bmod (k+1)) \equiv a_i - (a_i \bmod (k+1)) \equiv 0 \pmod{k+1}.$$

Therefore every output number is divisible by $k+1$. Since $k \ge 1$, we have $k+1 \ge 2$, so the gcd of the whole output array is at least $k+1$, definitely greater than $1$.

Bounds

The largest added value is at most:

$$k \cdot k = k^2.$$

So every output value is at most:

$$10^9 + k^2,$$

which matches the required output bound. Use long long, because $k^2$ can be around $10^{18}$.

Complexity

For each element, we do one modulo and one multiplication.

Time complexity: $O(n)$ per test case.

Memory complexity: $O(1)$ besides the input/output storage.