题解

题意简述

给定一个长度为 $n$ 的正整数序列 $a$，问是否可以通过重新排列，使得存在一个分界点 $i$（$1 \le i < n$），满足：

$$\min([a_1, a_2, \dots, a_i]) = \gcd([a_{i+1}, a_{i+2}, \dots, a_n]) $$

---

思路分析

1. 基本观察

对于任意正整数序列，一定有 $\gcd \le \min$。
设全局最小值为 $x$，即 $x = \min(a)$。

由于左边取的是前缀最小值，右边取的是后缀 GCD，并且两者相等，所以这个相等的值必须就是 $x$（因为 $x$ 不可能出现在右边作为 GCD 而比左边的最小值大，反之亦然）。

因此，我们实际需要满足的条件是：

• 左边的最小值 $= x$
• 右边的 GCD $= x$

---

2. 左边的最小值为 $x$ 的条件

为了让左边的最小值恰好为 $x$，只需把所有小于 $x$ 的数（实际上没有）或者等于 $x$ 的数放在左边，并且至少有一个 $x$ 放在左边。如果所有 $x$ 都放在右边，左边的最小值会大于 $x$（因为右边最小的 $x$ 在左边没有出现），就不满足条件。

更简单的理解：至少把一个 $x$ 放在左边即可，因为左边取最小值时一定是 $x$（除非左边没有任何 $x$，但那样最小可能 > $x$）。

但更方便的方式是：我们把一个 $x$ 固定到左边，剩下的元素（包括可能还有其他的 $x$）放到右边，然后检查右边的 GCD 能否为 $x$。

---

3. 右边的 GCD 为 $x$ 的条件

设 $x$ 在数组中出现次数为 $cnt_x$。
我们拿出一个 $x$ 放到左边，则右边剩下的元素包括：

• 剩下的 $cnt_x - 1$ 个 $x$
• 所有不是 $x$ 的其他数

右边的 GCD 要等于 $x$，这意味着：

1. 右边所有数都必须是 $x$ 的倍数（否则 GCD 不可能是 $x$）。
2. 右边所有数去除公因数后，留下的 GCD 必须为 1（即它们不能有大于 1 的公共因子，否则整体 GCD 会大于 $x$）。

---

4. 贪心策略

为了满足条件，我们可以这样安排：

• 将所有 $x$ 的倍数（除了一个我们拿出来放到左边的 $x$）都放到右边。
• 这些数的 GCD，如果仍然等于 $x$，则可行；否则不可行。

为什么这是最优的？
因为右边如果包含非 $x$ 倍数的数，GCD 不可能是 $x$（因为 $x$ 不整除它）。
而把所有 $x$ 的倍数都放在右边，可以最大化右边集合，这能最小化 GCD，因为多放数可能会引入更多公因子吗？等一下，实际上多放数可能会让 GCD 变小（因为多了数，公共因子更少），但这里我们希望 GCD 恰好等于 $x$，所以把所有倍数放进去，去除 $x$ 后，如果它们 GCD 等于 $x$，就成功；如果大于 $x$，说明它们有超过 $x$ 的公共因子，不行。

实际上，正确推导是：右边的数必须全是 $x$ 的倍数，且它们的 GCD 必须正好是 $x$。所以我们从全部 $x$ 的倍数（去掉一个 $x$）求 GCD 即可。

---

5. 详细证明

设 $S = \{a_i \mid a_i \bmod x = 0\}$，即 $x$ 的倍数的集合。
我们把其中一个 $x$ 放到左边，右边放 $S \setminus \{x\}$ 以及所有不是 $x$ 倍数但 $<x$ 的数？不对，如果右边有不是 $x$ 倍数的数，GCD 不可能是 $x$，所以右边必须全部是 $x$ 的倍数。

因此右边 = 所有 $x$ 的倍数（包含可能剩余的 $x$）去掉一个 $x$。

那么 GCD 右边 = $\gcd(\{b \in S \mid b \neq x\})$。

如果这个 GCD 等于 $x$，则可行。否则不可行。

---

6. 算法步骤

1. 找到数组的最小值 $x$。
2. 遍历数组，找出所有是 $x$ 倍数且不等于 $x$ 的数（即大于 $x$ 的倍数），并计算它们的 GCD。
3. 如果这个 GCD 等于 $x$，输出 "Yes"，否则 "No"。

注意：如果 $x$ 出现次数 $>1$，那么我们去掉一个 $x$ 后，右边还有 $x$，这不会影响 GCD 最终为 $x$（因为 $x$ 本身是 $x$ 的倍数，并且 $\gcd(x, something) = \gcd(x, something)$）。所以只要 $x$ 的倍数的 GCD 为 $x$ 即可。

---

复杂度分析

每个测试用例需要 $O(n)$ 时间找最小值，$O(n)$ 时间求 GCD，GCD 时间复杂度 $O(\log a)$。
总复杂度 $O(\sum n \log \max a)$，符合要求。

---

代码实现

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T, n;
    cin >> T;
    while (T--) {
        cin >> n;
        vector<ll> a(n);
        for (ll &x : a) {
            cin >> x;
        }
        // 找到最小值的下标
        int p = min_element(a.begin(), a.end()) - a.begin();
        ll x = a[p];
        ll g = 0;
        for (int i = 0; i < n; ++i) {
            if (i != p && a[i] % x == 0) {
                g = __gcd(g, a[i]);
            }
        }
        cout << (g == x ? "Yes\n" : "No\n");
    }
    return 0;
}