How many times can the prefix $$$\gcd$$$ sequence $$$x_i = \gcd(a_1,\dots,a_i)$$$ change?

It changes at most $$$O(\log A)$$$ times since each change makes it at least half.

After removing one element from a segment, what condition must the remaining $$$\gcd$$$ satisfy to become a target value after one modification?

You need:

where $$$g$$$ is the $$$\gcd$$$ after removal and $$$t$$$ is the target.

Define a function

For each index $$$i$$$, let

and define

We need to count all $$$i$$$ such that $$$f(P_i, S_i) = 1$$$.

A modification consists of changing at most one element in $$$P_i \cup S_i$$$. Observe that changing an element is equivalent to removing it and replacing it with a suitable value, hence it suffices to consider removal.

Thus, for a fixed $$$i$$$, the following cases arise:

(1) No modification:

(2) One removal in prefix: There exists $$$j \le i$$$ such that

(3) One removal in suffix: There exists $$$k \gt i$$$ such that

Hence,

Using the property that gcd values over prefixes and suffixes form at most $$$O(\log A)$$$ distinct values, we can efficiently maintain all possible gcds obtained by removing one element. Precomputing $$$x_i$$$ and $$$y_i$$$, and iterating over $$$i$$$, we check the above conditions in total $$$O(n \log A)$$$ time.

Lemma 1. (Prefix $$$\gcd$$$ changes $$$O(\log A)$$$ times)

Let $$$x_i = \gcd(a_1,\dots,a_i)$$$. Then $$$x_i$$$ takes $$$O(\log A)$$$ distinct values.

Proof.

If $$$x_{i+1} \ne x_i$$$, then $$$x_{i+1}$$$ is a proper divisor, so:

Thus after $$$k$$$ changes: $$$x_i \le A/2^k \ge 1 \Rightarrow k \le \log_2 A$$$.

Lemma 2. (Divisibility condition is sufficient and necessary)

Let $$$g = \gcd(P_i \setminus {a_j})$$$. Then one modification makes $$$\gcd(P_i)=y_i$$$ iff:

Proof.

If $$$y_i \mid g$$$, replace $$$a_j$$$ with $$$y_i$$$: $$$\gcd(g, y_i) = y_i$$$