首先，我们来思考我们要构造的是什么。
我们要构造的是一个无论怎样操作字典序都会变小的序列，且这个序列的字典序是最小的。
然后考虑字典序会变大的条件。
如果字典序变大了，那么一定是在前 \(i-1\) 位不变的前题下，\(i\) 位的变大了。那么变大的一定是从后面来的。
而我们考虑所有的数对 \((a_i,a_j)\)，我们发现，一旦 \(\gcd(a_i,a_j)>1\)，那么无论怎么移动，\(i\) 和 \(j\) 的位置关系不会改变，因为要改变就一定要交换，而只能相邻互质的交换。
那么，先给出结论：
- 无论怎么操作，字典序都不会变大，当且仅当对于所有数对 \((i,j)\)，如果有 \(a_i<a_j\)，则 \([i,j)\) 中一定存在和 \(a_j\) 不互质的数。
考虑证明，首先，如果对某个 \(j\) 不存在，那么我们可以把 \(a_j\) 交换到 \(a_i\)，显然更大。
如果每个数都存在，对 \(a_j\)，考虑这个数 \(a_x\)，首先 \(a_j\) 一定在 \(a_x\) 的后面，然后要么 \(a_x\) 也不能到达 \(a_i\)，要么 \(a_x\le a_i\)。前一种情况数学归纳，后一种情况把 \(a_x\) 交换到 \(a_i\)，字典序要么变小，要么相同，但是即使相同，因为本来就没人能替换 \(a_x\)，所以 \(a_x\) 就可以放在这里，这又是一个数学归纳法。所以我们能从“长度 \(n-1\) 的成立”分别推得任何前缀和后缀都成立，然后就可以推 \(n\) 成立。对于 \(1\) 显然成立，所以对任意的 \(n\) 都成立。
这样我们就证明了这个结论。来思考做法。
首先，这种字典序最小的，\(99%\) 是贪心，我们一位位从小到大枚举，每次找到一个没有出现过的 \(k\)，填上在位置 \(i\)，然后判断剩下的数是否存在一种排列，使得 后面的数不会对任何前面的数造成影响 。至于后面的数自己会不会对自己造成影响，我们不去理会。
首先，我们要满足 \(k\) 对前 \(i-1\) 位不会影响。我们可以暴力往前跑，遇到不互质的跳出，遇到比它小的判否。
然后考虑什么时候存在这个排列。首先考虑哪些数可以在自己到 \(k\) 之前不需要有任何和自己不互质的数，也不会对前 \(i\) 个数造成影响。我们可以 \(O(n)\) 的判断每个数是否合法，也就是尝试把它放在 \(i+1\)，和前面的相同。
我们先把这些数都放上，然后对于后面的所有的数，都要求前面放上的数已经出现了和自己不互质的数。可以暴力判断。
则每一位的判断是 \(O(n^3)\)，一共进行 \(O(n^2)\) 次判断。
然后我们考虑优化这个做法，我们聚焦于每个数的所有质因子。我们储存所有的数的所有质因子和包含每个质因子的所有数。一共有 \(O(n\log a)\) 个。
接下来，我们发现，判否的情况就可以优化到 \(O(\log a)\) 的，我们可以记录所有质因子上一次出现的位置，然后预处理区间最小值，直接看每个数的质因子里面出现位置最靠后的位置 \(+1\) 到自己有没有比自己小的即可。
然后，我们还可以优化后面的判断，在每次加入一个数的时候，我们都把所有包含这个质因子的数加入队列里，然后暴力模拟判断能否填满。
复杂度一下就被优化到 \(O(n^3\log a)\) 了。
接下来考虑一个叫“池子”的东西。这个池子里面放的是放在第 \(i\) 位不会影响前 \(i-1\) 位的所有数。
然后我们建立一个图，每个数和所有和自己不互质的数连边。我们发现，只要一个连通子图中，只要有一个数被加入“池子”，它的所有邻居就可以加入队列……直到整个子图都被加入队列。
我们就可以在枚举数之前，先建立连通子图，然后把能放进去的数放进池子里。首先，我们不需要考虑某个子图没法被加入池子里的情况，因为我们在每次贪心的时候都会保证和前面不冲突。接下来，我们枚举我们把池子里的哪个数放在当前位置。当然是越小越好。
然后，对于所有和它不在同一子图中的池子里的数，一定和它互质（否则两者会连通）。那么它们要放到当前的后面，就必须比它小。也就是，所有连通子图（不包括自己）被放进池子中的数的最小值都不能大于它。
但是我们发现不包括自己是句废话，因为它自己就小于等于它自己了。
那么，我们就得到一个算法，每次贪心之前，用并查集找到连通子图，然后 \(O(n)\) 枚举所有数，\(O(\log a)\) 判断是否放进池子，以此处理出每个连通子图被放进池子的最小值。然后对每个连通子图找到最大值。从最大值开始遍历直到找到最小的池子里的数，填在这一位，更新最小值和它的所有质因子的出现位置。
结果我们发现，这个东西是 \(O(n\sqrt{a}+n\log n\log a+n^2\log a+n^3\log n)\) 的！瓶颈在连通子图！！！（前面是预处理质因子）
这是很离谱的，我们优化了半天等于没优化。我们即使预处理所有互质对，每次也要 \(O(n^2)\) 遍历所有边建图。而并查集优化也没辙，因为它是连通性分裂，又是天然的强制在线。
但是我们可以考虑质因子优化建图。我们可以把每个数和自己的质因子连边，这样点数和边数都是 \(O(n\log a)\) 了。在这个图上连通和原来暴力处理不互质的连边是等价的，还省去了一开始 \(n^2\) 次求 \(\gcd\)。
这样，我们得到了一个 \(O(n^2\log n\log a)\) 的做法。\(\log n\) 来自并查集，可以通过路径压缩和启发式合并同时使用优化到 \(O(n^2\alpha(n)\log a)\)。
然后就可以过了，\(\log a\) 是本质不同质因子个数的 \(\log\)，所以常数奇小，足以比很多 \(n^2\) 次 \(\gcd\) 建图的做法优。
int n,a[2005],del[2005],cnt;
int fa[200005],sz[200005],mn[200005],res[200005];
int lst[200005],bst[2005],ans[2005];
map<int,int>pri;
vt<int>ve[2005];
inline int head(int x){
return fa[x]==x?x:fa[x]=head(fa[x]);
}
inline void merge(int x,int y){
x=head(x),y=head(y);
if(x==y)return;
if(sz[x]<sz[y])swap(x,y);
sz[x]+=sz[y];
fa[y]=x;
}
inline void build(){
rep(i,1,n+cnt)fa[i]=i,sz[i]=1,mn[i]=1e9,res[i]=0;
rp(i,n)if(!del[i])for(auto j:ve[i])merge(i,n+j);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
rp(i,n)cin>>a[i];
sort(a+1,a+1+n);
rp(i,n){
int d=a[i];
for(int j=2;j*j<=d;j++){
if(d%j==0){
if(!pri.count(j))pri[j]=++cnt;
ve[i].pb(pri[j]);
}
while(d%j==0)d/=j;
}
if(d>1){
if(!pri.count(d))pri[d]=++cnt;
ve[i].pb(pri[d]);
}
}
rp(i,n)bst[i]=1e9;
rp(i,n){
build();
int mnn=0;
rp(j,n)if(!del[j]){
int nx=0;
for(auto x:ve[j])nx=max(nx,lst[x]);
if(bst[nx+1]>=a[j]){
res[j]=1;
mn[head(j)]=min(mn[head(j)],j);
}
}
rp(j,n)if(!del[j]&&fa[j]==j)mnn=max(mnn,mn[j]);
rep(j,n+1,n+cnt)if(fa[j]==j&&sz[j]>1)mnn=max(mnn,mn[j]);
rp(j,n)if(!del[j]&&res[j]){
if(j>=mnn){
ans[i]=j;del[j]=1;
for(auto x:ve[j])lst[x]=i;
break;
}
}
bst[i]=a[ans[i]];
per(j,1,i-1){
bst[j]=min(bst[j+1],a[ans[j]]);
}
}rp(i,n)cout<<a[ans[i]]<<" ";
cout<<endl;
return 0;
}
//Crayan_r
这份代码也调了很久，错因如下：
-
\(a_i\) 和 \(i\) 之间的使用混乱导致错误
-
\(lst\) 数组的值域可能达到 \(n\log n\)，开小了
-
并查集合并之前没有检查是否在同一集合内
其中，第三个错误我整整调了 1h，可见低级错误往往成为我们在高难度题目的最后一道关卡。
但是还是可以再优化的，我们可以把并查集换成 dfs，也就得到了一个 \(O(n^2\log n)\) 的做法。但是因为 \(\alpha(n)\) 实在很小，递归 dfs 又太慢，优化实在不明显。实际上，加上了 dfs 优化和不加入只被一个数包含的质因子优化之后，我们的程序从 122ms 被感人的优化到了 123ms。
不过，因为 dfs 可以直接指定从位置开始，dsu 可能会把质因子当根，所以 dfs 做法还是好写一点。
int n,a[2005],del[2005],cnt;
int mn[200005],col[200005],app[200005];
int lst[200005],bst[2005],ans[2005],vis[200005],res[2005];
map<int,int>pri;
vt<int>ve[2005];
vt<int>vv[200005];
inline void dfs(int x,int c){
vis[x]=1;
if(x<=n)col[x]=c;
for(auto j:vv[x])if(!vis[j])dfs(j,c);
}
inline void build(){
rep(i,1,n)col[i]=0,mn[i]=1e9,vis[i]=del[i],res[i]=0;
rep(i,n+1,n+cnt)vis[i]=0;
rp(i,n)if(!del[i]&&!vis[i])dfs(i,i);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
rp(i,n)cin>>a[i];
sort(a+1,a+1+n);
rp(i,n){
int d=a[i];
for(int j=2;j*j<=d;j++){
if(d%j==0){
if(!pri.count(j))pri[j]=++cnt;
ve[i].pb(pri[j]);app[pri[j]]++;
}
while(d%j==0)d/=j;
}
if(d>1){
if(!pri.count(d))pri[d]=++cnt;
ve[i].pb(pri[d]);app[pri[d]]++;
}
}
rp(i,n)for(auto j:ve[i])if(app[j]>1){
vv[i].pb(j+n);
vv[j+n].pb(i);
}
rp(i,n)bst[i]=1e9;
rp(i,n){
build();
int mnn=0;
rp(j,n)if(!del[j]){
int nx=0;
for(auto x:ve[j])nx=max(nx,lst[x]);
if(bst[nx+1]>=a[j]){
res[j]=1;
mn[col[j]]=min(mn[col[j]],j);
}
}
rp(j,n)if(!del[j]&&col[j]==j)mnn=max(mnn,mn[j]);
rep(j,mnn,n)if(!del[j]&&res[j]){
ans[i]=j;del[j]=1;
for(auto x:ve[j])lst[x]=i;
break;
}
bst[i]=a[ans[i]];
per(j,1,i-1)bst[j]=min(bst[j+1],a[ans[j]]);
}rp(i,n)cout<<a[ans[i]]<<" ";
return 0;
}
//Crayan_r