Summmon

What the operation really does

The operation

$$b_{i+1} := b_{i+1} \pm b_i$$

is an integer row operation. Repeating adjacent row operations lets us add any integer combination of earlier original values into a later position.

So for a fixed subarray

$$[a_l,a_{l+1},\dots,a_r],$$

the final value at position $i>l$ can be any integer of the form

$$a_i + c_l a_l + c_{l+1}a_{l+1}+\dots+c_{i-1}a_{i-1}.$$

That means the exact reachable condition is

$$x_i \equiv a_i \pmod{\gcd(a_l,a_{l+1},\dots,a_{i-1})}.$$

The first value $a_l$ itself is fixed.

This is the big invariant. Once you have it, the problem stops being cursed.

The subarray formula

Fix the left endpoint $l$. Let

$$x=a_l.$$

First, suppose every later value in the subarray is divisible by $x$. Then for every $i>l$, we have

$$a_i \equiv 0 \pmod x,$$

so we can choose the final value of every position to be exactly $x$. Therefore

$$f=0.$$

Now suppose there is some first index $p>l$ such that

$$a_p \not\equiv 0 \pmod x.$$

Before $p$, all values are divisible by $x$, so all earlier final values are multiples of $x$. Position $p$ must stay congruent to $a_p$ modulo $x$.

Let

$$rem = a_p \bmod x.$$

The closest a number with residue $rem$ modulo $x$ can get to a multiple of $x$ is

$$D=\min(rem,x-rem).$$

So every valid final array has range at least $D$.

That gives the lower bound. Now we need to show it is actually achievable.

If $rem\le x-rem$, use the interval

$$[x,x+D].$$

Otherwise, use

$$[x-D,x].$$

All positions before $p$ can be set to $x$. Position $p$ can be set to the other endpoint of this interval.

After processing $p$, the running gcd becomes

$$g=\gcd(x,a_p)=\gcd(x,rem).$$

Since $g$ divides both $rem$ and $x-rem$, it divides $D$, so in particular

$$g\le D.$$

Every later modulus divides this $g$, so every later modulus is also at most $D$. Any integer interval of length $D$ contains a representative of every residue modulo any number $\le D$. So every later value can also be placed inside the same interval.

Therefore the lower bound is tight:

$$f([a_l,\dots,a_r]) = D$$

for every $r\ge p$.

So the entire subarray behavior is hilariously simple:

• find the first element to the right that is not divisible by $a_l$;
• its circular distance to a multiple of $a_l$ is the answer for all subarrays ending at or after that point;
• if no such element exists, contribution is $0$.

Summing over all subarrays

For each left endpoint $l$, define $p_l$ as the first index greater than $l$ such that

$$a_{p_l} \not\equiv 0 \pmod {a_l}.$$

If there is no such index, left endpoint $l$ contributes nothing.

Otherwise, every right endpoint

$$r\in[p_l,n]$$

contributes the same value

$$D_l=\min(a_{p_l}\bmod a_l,\ a_l-(a_{p_l}\bmod a_l)).$$

There are

$$n-p_l+1$$

such right endpoints, so the total contribution of this $l$ is

$$(n-p_l+1)D_l.$$

Finding $p_l$ fast

We need the first position to the right that is not divisible by $a_l$.

A range $[L,R]$ consists only of multiples of $a_l$ iff

$$a_l \mid \gcd(a_L,a_{L+1},\dots,a_R).$$

So build a gcd sparse table. For a fixed $l$, the predicate

$$\gcd(a_{l+1},\dots,a_m) \not\equiv 0 \pmod {a_l}$$

is false before the first bad position and true from there onward. Binary search it.

Each gcd query is $O(1)$, each left endpoint uses $O(\log n)$ queries, and building the sparse table costs $O(n\log n)$.

Complexity

Per test case:

$$O(n\log n)$$

time and

$$O(n\log n)$$

memory.

The answer can exceed 64-bit, so use __int128. long long is not enough here; it gets cooked.