赛时在想一些奇怪的东西，没想到建图。
考虑使用元素两两之间的相对顺序来描述序列。发现若 \(x, y\) 互质那么它们的相对顺序被确定了。
先把输入的序列从小到大排序。然后考虑互质的数之间先连一条无向边。那么先手要把无向边定向使得它是个 DAG，后手会求出这个 DAG 的最大拓扑序。也就是说先手要最小化这个 DAG 的最大拓扑序。
考虑把所有点的边按编号从小到大排序，然后从小到大遍历这个图，从小到大遍历出边，这样会形成一个生成森林，边从祖先定向到儿子即可。
考虑这样贪心为什么是对的。发现若先遍历更大的点 \(v_2\) 肯定不优，因为若先遍历更小的点 \(v_1\)，说不定就在遍历 \(v_1\) 的过程中访问了 \(v_2\)，就能使得不用添加 \(u \to v_2\) 的边。所以是不优的。
时间复杂度为 \(O(n^2 (\log V + \log n))\)，\(\log V\) 为求 \(\gcd\) 复杂度。
code
// Problem: E - Rearranging
// Contest: AtCoder - AtCoder Grand Contest 010
// URL: https://atcoder.jp/contests/agc010/tasks/agc010_e
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 2020;
int n, a[maxn], ind[maxn];
bool vis[maxn];
vector<int> G[maxn];
void dfs(int u) {
vis[u] = 1;
for (int v = 1; v <= n; ++v) {
if (!vis[v] && __gcd(a[u], a[v]) > 1) {
G[u].pb(v);
++ind[v];
dfs(v);
}
}
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
dfs(i);
}
}
priority_queue<pii> pq;
for (int i = 1; i <= n; ++i) {
if (!ind[i]) {
pq.emplace(a[i], i);
}
}
while (pq.size()) {
int u = pq.top().scd;
pq.pop();
printf("%d ", a[u]);
for (int v : G[u]) {
if (!(--ind[v])) {
pq.emplace(a[v], v);
}
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}