因为只有相邻的互质的 \(a_i\) 可以交换，那么就说明不互质的 \(a_i\) 无法相交换，对应的位置关系也就不会改变。
于是可以考虑图论建模，对于 \(\gcd(a_i, a_j) > 1\)，连边 \((i, j)\)。
那么对于先手，就相当于要把这些边定向，变为一个 DAG。
而后手因为要保证最大，所以肯定是在 DAG 上跑拓扑的时候每次去取最大的点。
于是就考虑先手如何使得后手弄出来的最小。
那么首先，对于一个连通块，先手肯定会把最小的数 \(x\) 放在最前面，因为后面大的就换不到前面来了。
其次，考虑找到与 \(x\) 有连边的 \(y\)，那么选上 \(y\)，这样就能保证选完 \(x\) 后让后手选到的尽量小了，然后同样的递归 \(y\) 去处理。
若此时还有与 \(x\) 有连边的点没有被确定，又从中选最小的递归下去。
这部分的正确性相当于是保证了，越小的点能够走出去的点是越广的，对于后手选大的贪心就会使得选最大的后面能走的点相对来说没那么广和优，所以是对的。
时间复杂度 \(\mathcal{O}(n^2\log V + n\log n)\)，\(V\) 为值域。
#include<bits/stdc++.h>
const int maxn = 2e3 + 10;
int n;
int a[maxn], vis[maxn];
std::vector<int> to[maxn];
void dfs(int u) {
vis[u] = 1;
for (int v = 1; v <= n; v++)
if (! vis[v] && (! u || std::__gcd(a[u], a[v]) > 1))
to[u].push_back(v), dfs(v);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
std::sort(a + 1, a + n + 1);
dfs(0);
std::priority_queue<int> Q;
for (int u : to[0]) Q.push(u);
for (int i = 1, u; i <= n; i++) {
u = Q.top(); Q.pop();
printf("%d ", a[u]);
for (int v : to[u]) Q.push(v);
}
return 0;
}