No Cost Too Great (Hard Version)

The key fact is simple:

Two numbers have gcd greater than $1$ iff they share at least one prime factor.

So every successful plan is secretly choosing a prime $p$ and making two values divisible by $p$.

The cheap upper bound

Pick the two indices with the smallest operation costs. Call their costs $b_1$ and $b_2$ after sorting conceptually by cost.

We can always make both chosen values even. Each one needs either $0$ or $1$ increment, so the total cost is at most

$$b_1+b_2.$$

This is our baseline answer. It is also the hammer that smashes the search space.

Why big moves are rare

Suppose we are looking at some chosen pair.

If both elements are incremented at least twice, then the cost is already at least

$$2b_i+2b_j,$$

while making those same two elements even costs at most

$$b_i+b_j.$$

So that is never optimal. Easy deletion.

If one element is incremented at least twice and the other is incremented once, the same kind of domination happens:

$$k b_i + b_j \ge b_i+b_j \quad (k\ge 2),$$

and again making the pair even is no worse.

Therefore, if an optimal solution has a “big move” of $k\ge 2$ increments, the other element must be left unchanged.

Now ask: which element is allowed to receive this big move?

Let $s$ be an index with minimum cost $b_s$. Suppose some other index $x$ gets $k\ge 2$ increments. That costs

$$k b_x.$$

But we could instead make indices $x$ and $s$ both even, costing at most

$$b_x+b_s \le 2b_x \le k b_x.$$

So a non-cheapest element doing multiple increments is also dominated. Brutal, but fair.

Conclusion:

• Nobody needs more than one increment, except possibly the cheapest-cost element.
• If the cheapest-cost element gets multiple increments, the other element stays unchanged.

That gives us the full case split.

Case 1: zero increments

We need two original values sharing a prime factor.

Precompute the distinct prime factors of every number up to $2\cdot 10^5+1$. Then scan all $a_i$ and count which prime factors have appeared. If a prime factor appears in two different elements, answer is $0$.

Case 2: exactly one increment total

Try incrementing each index $i$ once. We need $a_i+1$ to share a prime factor with some other original value.

Use the same prime-factor counts. Temporarily remove the factors of $a_i$ from the counts so we do not accidentally match the element with itself. Then check the factors of $a_i+1$. If any of them still appears, we can achieve the goal with cost $b_i$.

So update:

$$ans = \min(ans, b_i).$$

What about one increment on both elements?

That costs at least the sum of two operation costs, so it is never better than the baseline $b_1+b_2$. We already have that covered. No need to chase that rabbit hole.

Case 3: multiple increments on one element

Only the cheapest-cost index can matter. Let it be $s$.

The other chosen element must stay unchanged, so the common prime must be one of the prime factors of some original value $a_j$ where $j\ne s$.

For every such prime $p$, compute how many increments are needed to make $a_s$ divisible by $p$:

$$add = (p - a_s \bmod p) \bmod p.$$

The cost is

$$add\cdot b_s.$$

Take the minimum over all prime factors of all other original elements.

That is it. The problem looks like “maybe arbitrary increments,” but the cost ordering forces almost everything into $0$ or $1$ increments. The only wild card is the cheapest index, and even that only has to aim at primes already present somewhere else.

Complexity

Let $A=2\cdot 10^5+1$. Precomputing distinct prime factors takes

$$O(A\log\log A).$$

Each test case processes the prime factors of $a_i$ and $a_i+1$, so the total work is

$$O(n\cdot \omega(A)),$$

where $\omega(x)$ is the number of distinct prime factors. Under these constraints, that is very comfortably fast.