Alright guys, round 3.

I have a piece of code that looks reasonable, passes the examples I tried, and has absolutely no intention of telling me where it goes wrong.

Your job is to prove me wrong.

The problem

You are given an array of positive integers (a).

You can perform the following operation any number of times:

Choose two distinct indices (i,j) such that (a_i \ge a_j), and replace

[ a_i \gets a_i-a_j. ]

Determine whether it is possible to make all elements equal.

My solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int &x : a)
            cin >> x;

        sort(a.begin(), a.end());

        bool ok = true;

        for (int i = 1; i < n; i++) {
            if (a[i] % a[0] != 0) {
                ok = false;
                break;
            }
        }

        cout << (ok ? "YES" : "NO") << '\n';
    }
}

Looks fine, right?

We sort the array, take the smallest element, and check whether every other element is divisible by it.

If all of them are multiples of the smallest element, surely we can reduce them until they match.

...right?

Your mission

1. Find a valid counterexample.
2. Explain why the answer printed by my code is wrong.
3. Give the correct condition and prove it.
4. Can you solve it without simulating the operations?

Constraints:

• (1 \le t \le 10^4)
• (2 \le n \le 2\cdot 10^5)
• (1 \le a_i \le 10^9)
• The sum of (n) over all test cases is at most (2\cdot 10^5).

No random giant test case with 200,000 numbers, please. I want a counterexample that hurts my code with as few numbers as possible.

If you find one, post it in the comments and explain the reasoning. If someone beats you to it, find a smaller one.

And don't just drop code. Convince us that your condition is necessary and sufficient.

Let's see who gets it first.