No Cost Too Great (Easy Version)

The easy version has one massive simplification: every increment costs exactly $1$. So we are not choosing between cheap and expensive elements. The cost is literally just "how many +1 moves did we do?"

Key bound

The answer is never more than $2$.

Why? Pick any two indices. If both numbers are odd, increment both once and they become even. If one is already even, increment the odd one once. If both are already even, you needed $0$ moves. In all cases, after at most $2$ moves, those two chosen values are both divisible by $2$, so their gcd is at least $2$.

So the whole problem collapses to deciding between only three answers:

• $0$: already good
• $1$: one increment can make it good
• $2$: otherwise

No hidden $17$-move nonsense. The ceiling is $2$.

When is the answer 0?

We need some pair with gcd greater than $1$. That means the two numbers share at least one prime factor.

So factor every $a_i$ into its distinct prime factors. If any prime appears in two different array elements, then those two elements already share that prime, and the answer is $0$.

Important detail: for one number like $12 = 2^2 \cdot 3$, prime $2$ should only be counted once for that number. We care about how many indices contain the prime, not how many times it appears inside one value.

When is the answer 1?

If the answer is $1$, then exactly one number changes from $a_i$ to $a_i+1$. The other number in the pair stays unchanged.

So we need some prime $p$ such that:

• $p$ divides $a_i+1$
• $p$ divides some original $a_j$ with $j \ne i$

That is enough, because then $gcd(a_i+1,a_j) \ge p > 1$.

After we have already ruled out answer $0$, we can store all primes that appear in the original array. Then for every $a_i+1$, factor it. If any of its prime factors appeared in the original array, answer $1$.

You do not even need to subtract the current index from the frequency. A prime dividing $a_i+1$ cannot divide $a_i$, because consecutive numbers are coprime. So if that prime appeared originally, it appeared in some other element. Clean little math trick, no drama.

Otherwise answer 2

If neither $0$ nor $1$ works, then by the earlier bound, $2$ must work. Just make two numbers even.

Algorithm

For each test case:

1. Factor every original $a_i$.
2. Count how many different elements contain each prime.
3. If any prime count reaches $2$, print $0$.
4. Otherwise, for each $a_i$, factor $a_i+1$.
5. If any prime factor of $a_i+1$ has positive original frequency, print $1$.
6. Otherwise print $2$.

The maximum value we need to factor is $200000+1$, so a smallest-prime-factor sieve is perfect.

Complexity

Precompute smallest prime factors up to about $200001$ once.

Each number is factored in roughly logarithmic time, so the total work is easily fine for $\sum n \le 2 \cdot 10^5$.

Overall complexity: $O(M \log\log M + N \log M)$, where $M=200001$ and $N$ is the total number of array elements.