Who wins when all elements of $$$a$$$ are equal?

Who wins when $$$a = [1, 1, 1, \dots, 1, x]$$$ where $$$x \gt 1$$$?

How can this configuration be forced during the game?

Let $$$g = \gcd(a_1, a_2, \dots, a_n)$$$.

Observe that dividing all elements by $$$g$$$ does not affect the game, since all gcd relations are preserved up to scaling. Hence, without loss of generality, we may assume $$$\gcd(a_1, a_2, \dots, a_n) = 1$$$.

Case 1: All elements are equal to $$$1$$$.

In this case, no valid move exists, since for any subsequence, all elements are equal to its gcd. Hence, Alice cannot make a move and therefore wins.

Case 2: The array is of the form $$$a = [1, 1, \dots, 1, x]$$$ where $$$x \gt 1$$$.

Any valid move must include the element $$$x$$$, since otherwise the subsequence consists only of $$$1$$$s and is invalid. If $$$x$$$ is included, the gcd of the chosen subsequence is $$$1$$$, and all selected elements become $$$1$$$. Thus, after one move, the array becomes identically $$$1$$$.

Therefore, the player making this move leaves no valid moves for the opponent. Hence, Alice loses and Bob wins.

Case 3: $$$n = 2$$$ and the array is not covered by the above cases.

Since $$$\gcd(a_1, a_2) = 1$$$, the only valid move is to select both elements, after which the array becomes $$$[1,1]$$$. This reduces the game to Case 1, so Bob wins.

Case 4: All remaining cases.

Consider all subsequences of size $$$n-1$$$. We claim that if there exists at least one such subsequence with gcd equal to $$$1$$$, then Alice wins; otherwise, Bob wins.

Conclusion:

• If all elements are $$$1$$$, Alice wins.
• Else if the array is of the form $$$[1, 1, \dots, 1, x]$$$, Bob wins.
• Else if $$$n = 2$$$, Bob wins.
• Otherwise, check if there exists a subsequence of size $$$n-1$$$ with gcd $$$1$$$:
• If yes, Alice wins.
• Otherwise, Bob wins.

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
 
void solve() {
    ll n;
    cin >> n;

    vector<ll> a(n);
    for (ll i=0; i<n; i++) cin >> a[i];
    ll g = 0;
    for (ll i=0; i<n; i++) {
        g = gcd(g, a[i]);
    }

    for (ll i=0; i<n; i++) a[i] /= g;

    if (n == 2) {
        if (a[0] == a[1]) {
            cout << "Alice" << endl;
        } else {
            cout << "Bob" << endl;
        }

        return;
    }

    ll one_cnt = 0;;
    for (ll i=0; i<n; i++) if (a[i] == 1) one_cnt++;

    if (one_cnt == n) {
        cout << "Alice" << endl;
        return;
    } else if (one_cnt == n-1) {
        cout << "Bob" << endl;
        return;
    }

    vector<ll> gcd_pref(n+2);
    vector<ll> gcd_suf(n+2);
    
    for (ll i=0; i<n; i++) {
        gcd_pref[i+1] = gcd(gcd_pref[i], a[i]);
    }
    for (ll i=n-1; i>=0; i--) {
        gcd_suf[i+1] = gcd(gcd_suf[i+2], a[i]);
    }

    for (ll i=1; i<=n; i++) {
        if (gcd(gcd_pref[i-1], gcd_suf[i+1]) == 1) {
            cout << "Alice" << endl;
            return;
        }
    }

    cout << "Bob" << endl;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 1;
    cin >> t;

    while (t--) solve();
    
    return 0;
}
```

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$$$