A Simple GCD Problem (Hard Version)

Observation 1: Adjacent GCDs Are Enough

The statement asks us to preserve the GCD of every subarray of length at least $2$. That sounds awful, but for any interval $[l,r]$,

$$\gcd(a_l,a_{l+1},\ldots,a_r) = \gcd\bigl(\gcd(a_l,a_{l+1}),\gcd(a_{l+1},a_{l+2}),\ldots,\gcd(a_{r-1},a_r)\bigr).$$

So preserving all adjacent values

$$g_i=\gcd(a_i,a_{i+1})$$

is necessary and sufficient. The monster was just a path DP wearing a fake mustache.

Observation 2: The Minimum Legal Value

For each index define

$$need_i= \begin{cases} g_1, & i=1,\\ g_{n-1}, & i=n,\\ \operatorname{lcm}(g_{i-1},g_i), & 1<i<n. \end{cases}$$

Every valid final value at $i$ must be divisible by $need_i$. Also $need_i\mid a_i$, because both adjacent GCDs divide $a_i$.

If $need_i\le b_i$ and $need_i<a_i$, then set $a'_i=need_i$ and count one operation. This is always optimal: if some larger multiple works with the neighbors, replacing it by $need_i$ still keeps each adjacent GCD exactly the same, because it only removes factors. Free operation, take it.

Let

$$c_i= \begin{cases} need_i, & need_i\le b_i,\\ a_i, & need_i>b_i. \end{cases}$$

The base candidate $c_i$ has cost $1$ if $c_i\ne a_i$, otherwise cost $0$.

Observation 3: Only Prime Multipliers Matter

If $c_i\ne a_i$, index $i$ is already changed, and multiplying it further gives no extra score. It can only make GCD collisions easier, which is useless.

If $c_i=a_i$, then changing index $i$ means choosing some value $a_i\cdot x$, where $x>1$ and $a_i x\le b_i$. If a composite $x$ works, then one prime factor $p\mid x$ also works, because $a_i p$ divides $a_i x$. So we only need prime multipliers.

We also do not need all primes. Fix the neighbors of $i$. A prime $p$ is bad only if it appears in the extra part of a neighbor beyond the required adjacent GCD. The product of the two relevant neighbor values is at most

$$10^9\cdot10^9=10^{18}.$$

But the product of the first $20$ primes, $2,3,5,\ldots,71$, is greater than $10^{18}$. Therefore the neighbors cannot forbid all of them. If $\lfloor b_i/a_i\rfloor$ is smaller than $71$, then every possible prime multiplier is already among these first primes anyway. That is the whole trick; miss it and the problem becomes a swamp.

DP

For each index $i$, build candidates:

• $c_i$, with cost $[c_i\ne a_i]$;
• if $c_i=a_i$, also $a_i\cdot p$ for each of the first $20$ primes satisfying $a_i p\le b_i$, with cost $1$.

Now run DP along the path:

$$dp[i][j]=\max\text{ operations on }1\ldots i \text{ if }a'_i\text{ is candidate }j.$$

A transition from value $x$ at $i-1$ to value $y$ at $i$ is legal iff

$$\gcd(x,y)=g_{i-1}.$$

So

$$dp[i][j]=cost(i,j)+\max_{k:\ \gcd(val_{i-1,k},val_{i,j})=g_{i-1}} dp[i-1][k].$$

Each position has at most $21$ candidates, hence the complexity is

$$O(n\cdot 21^2\cdot \log 10^9),$$

with $O(21)$ DP memory. This easily fits for $\sum n\le 5\cdot10^4$.

Reference checked: Codeforces Round 1089 editorial.