#### 分析

Let the answer be a1 ≤ a2 ≤ … ≤ an. We will use the fact that gcd(ai, aj) ≤ amin(i, j).

It is true that gcd(an, an) = an ≥ ai ≥ gcd(ai, aj) for every 1 ≤ i, j ≤ n. That means that an is equal to maximum element in the table. Let set an to maximal element in the table and delete it from table elements set. We’ve deleted gcd(an, an), so the set now contains allgcd(ai, aj), for every 1 ≤ i, j ≤ n and 1 ≤ min(i, j) ≤ n - 1.

By the last two inequalities gcd(ai, aj) ≤ amin(i, j) ≤ an - 1 = gcd(an - 1, an - 1). As soon as set contains gcd(an - 1, an - 1), the maximum element in current element set is equal to an - 1. As far as we already know an, let’s delete the gcd(an - 1, an - 1), gcd(an - 1, an),gcd(an, an - 1) from the element set. Now set contains all the gcd(ai, aj), for every 1 ≤ i, j ≤ n and 1 ≤ min(i, j) ≤ n - 2.

We’re repeating that operation for every k from n - 2 to 1, setting ak to maximum element in the set and deleting the gcd(ak, ak),gcd(ai, ak), gcd(ak, ai) for every k < i ≤ n from the set.

One could prove correctness of this algorithm by mathematical induction. For performing deleting and getting maximum element operations one could use multiset or map structure, so solution has complexity .

#### C++代码

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

multiset<int> st;
vector<int> res;

int main() {
int n; cin >> n;
for(int i = 0; i < n * n; ++i) {
int x; cin >> x;
st.insert(x);
}
res.push_back(*--st.end());
st.erase(--st.end());
while(!st.empty()) {
int cur = *--st.end();
st.erase(--st.end());
for(auto i : res) {
int g = __gcd(cur, i);
st.erase(st.find(g));
st.erase(st.find(g));
}
res.push_back(cur);
}
for_each(res.begin(), res.end(), [](const int i) { cout << i << " "; });
return 0;
}
```