There are $N$ integers written on a blackboard. The $i$-th integer is $A_i$.
Takahashi and Aoki will arrange these integers in a row, as follows:
- First, Takahashi will arrange the integers as he wishes.
- Then, Aoki will repeatedly swap two adjacent integers that are coprime, as many times as he wishes.
We will assume that Takahashi acts optimally so that the eventual sequence will be lexicographically as small as possible, and we will also assume that Aoki acts optimally so that the eventual sequence will be lexicographically as large as possible. Find the eventual sequence that will be produced.
Constraints
- $1 ≦ N ≦ 2000$
- $1 ≦ A_i ≦ 10^8$
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ … $A_N$
Output
Print the eventual sequence that will be produced, in a line.
Sample Input 1
5 1 2 3 4 5
Sample Output 1
5 3 2 4 1
If Takahashi arranges the given integers in the order $(1,2,3,4,5)$, they will become $(5,3,2,4,1)$ after Aoki optimally manipulates them.
Sample Input 2
4 2 3 4 6
Sample Output 2
2 4 6 3
先把 \(a\) 排序。
给一个序列，如何判断另一个序列是否可以有其转换出来。
对于两个不互质的数 \(u,v\)，他们在序列中的相对顺序不会改变。只要满足这个要求，排列就可以操作出来。
那么后手的最优策略就有了。建图然后用堆跑出字典序最大的拓扑序。
而先手就是要给出这个 DAG。建出图后，先手是要给一个无向图定向为 DAG，使得其字典序最大的拓扑序最小。
首先每个连通块是独立的。而且连通块中唯一的无入度的点一定是最小的那个点。现在在考虑一个点的所有出边怎么定向。
从小到大枚举出边，如果终点到达过，可以考虑下一个。否则就从这里深搜。为什么是深搜而不是广搜呢？因为有可能可以从某个点定向定回来这个出边。
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int n,a[N],p[N][N],in[N],vs[N];
priority_queue<int>q;
int gcd(int x,int y)
{
if(!y)
return x;
return gcd(y,x%y);
}
void dfs(int x)
{
vs[x]=1;
for(int v=1;v<=n;v++)
{
if(!p[x][v])
continue;
if(vs[v])
p[x][v]=p[v][x]=0;
else
p[v][x]=0,dfs(v);
}
}
void topo()
{
for(int i=1;i<=n;i++)
if(!in[i])
q.push(i);
while(!q.empty())
{
int k=q.top();
q.pop();
printf("%d ",a[k]);
for(int i=1;i<=n;i++)
{
if(p[k][i])
{
--in[i];
if(!in[i])
q.push(i);
}
}
}
}
int main()
{
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++)
for(int j=1;j<=n;j++)
if(i^j&&gcd(a[i],a[j])^1)
p[i][j]=p[j][i]=1;
for(int i=1;i<=n;i++)
if(!vs[i])
dfs(i);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(p[i][j])
in[j]++;
topo();
}