A Simple GCD Problem (Easy Version)

Kill the Fake Complexity

The statement asks for preserving the GCD of every subarray of length at least $2$. That sounds nasty, but it is mostly theater.

Define

$$c_i=\gcd(a_i,a_{i+1}) \quad (1\le i<n).$$

For any interval $[l,r]$ with $l<r$,

$$\gcd(a_l,a_{l+1},\ldots,a_r) = \gcd(c_l,c_{l+1},\ldots,c_{r-1}).$$

Why? The left side divides every adjacent-pair GCD. Conversely, if some number divides every adjacent-pair GCD, then it divides $a_l$ and $a_{l+1}$ from the first pair, then $a_{l+2}$ from the next pair, and so on. Therefore it divides the whole interval.

So the entire condition is equivalent to preserving every adjacent GCD $c_i$. The monster was a kitten.

What Can One Index Become?

In the easy version, $b_i=a_i$, so an operation can only replace $a_i$ by some smaller positive value.

For an internal index $i$, the new value $x_i$ must satisfy both adjacent edges:

$$\gcd(x_i,x_{i-1})=c_{i-1}, \qquad \gcd(x_i,x_{i+1})=c_i.$$

In particular, $x_i$ must be divisible by both $c_{i-1}$ and $c_i$. Therefore

$$\operatorname{lcm}(c_{i-1},c_i) \mid x_i.$$

Let

$$d_i= \begin{cases} c_1, & i=1,\\ \operatorname{lcm}(c_{i-1},c_i), & 2\le i\le n-1,\\ c_{n-1}, & i=n. \end{cases}$$

This $d_i$ is the smallest value index $i$ could possibly take while respecting its neighboring GCD requirements.

Since $c_{i-1}$ and $c_i$ both divide $a_i$, their LCM also divides $a_i$. Thus $d_i\le a_i$.

If $d_i=a_i$, index $i$ cannot be changed: every valid new value must be a multiple of $d_i$, but also must be at most $a_i$ and different from $a_i$. No room. Brutal.

If $d_i<a_i$, then changing $a_i$ to $d_i$ is at least locally possible.

Can We Change All Possible Indices at Once?

Yes. This is the only point where you should not hand-wave.

Consider an edge $(i,i+1)$. We need the final GCD to be $c_i$.

Each final value is either unchanged, or replaced by its $d$ value. In all cases, the value at position $i$ divides $a_i$ and is divisible by $c_i$ if it touches edge $i$. Same for position $i+1$.

So their GCD is at least $c_i$ and divides

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

Hence it is exactly $c_i$.

That proves all indices with $d_i<a_i$ can be changed simultaneously. Therefore the maximum number of operations is simply

$$\#\{i : d_i<a_i\}.$$

Complexity

We compute $n-1$ adjacent GCDs and one $d_i$ per index.

$$O(n\log A)$$

per test case, where $A=\max a_i$, and

$$O(n)$$

memory. Across all tests this is fine because $\sum n\le 2\cdot 10^5$.