自动搬运

查看原文

来自洛谷，原作者为

	littleKtian MoVe yoUR BoDy

搬运于2025-08-24 22:33:41，当前版本为作者最后更新于2021-09-08 18:53:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先点权相同的点显然可以缩在一起，这样剩下的点点权都是互不相同的。

因为当 $a_i\mid a_j$ 时 $\gcd(a_i,a_j)=a_i$，显然此时 $i$ 应该是 $j$ 的祖先。所以我们考虑按点权从大到小枚举 $i$，对于所有点权为其倍数的还未设置父亲的点 $j$，将 $j$ 的父亲设置为 $i$，全部设置完后再次枚举倍数检查是否成祖先关系（在这步之前要先检查是否连通）。

考虑如何处理类似 1 4 6 这种 $\gcd$ 未出现的情况。

我们可以枚举 $\gcd$ 的值，然后将点权为其倍数的点全部标记出来。可以发现如果所有被标记出来的点如果正好构成原树的一棵子树，那么这个 $\gcd$ 的值是不会出现的；如果为多棵，那么就必然会有点对使得点权的 $\gcd$ 的值为枚举到的值，也就是无解。

然后可以发现这步的判断可以和上面的判断合成一种判断。

复杂度 $O(n\log n)$（调和级数的复杂度）。

#include<bits/stdc++.h>
#define N 1000000
using namespace std;
int lw[100005],bi[100005][2],bs;
int n,a[100005],fa[100005],tt,rt;
int si[100005],hx[100005],dfn;
int xh[1000005];
int dr()
{
	int xx=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')xx=xx*10+ch-'0',ch=getchar();
	return xx;
}
void tj(int u,int v){bi[++bs][0]=lw[u],bi[lw[u]=bs][1]=v;}
void dfs(int w)
{
	si[w]=1,hx[w]=++dfn;
	for(int o_o=lw[w];o_o;o_o=bi[o_o][0])
	{
		int v=bi[o_o][1];
		dfs(v),si[w]+=si[v];
	}
}
bool gra(const int &x,const int &y){return hx[x]<=hx[y]&&hx[y]<hx[x]+si[x];}
int main()
{
	n=dr();
	for(int i=1;i<=n;i++)
	{
		a[i]=dr();
		if(xh[a[i]])fa[xh[a[i]]]=i,tj(i,xh[a[i]]),++tt;
		xh[a[i]]=i;
	}
	for(int i=N;i;i--)if(xh[i])
	{
		rt=xh[i];
		for(int j=i*2;j<=N;j+=i)if(xh[j]&&(!fa[xh[j]]))fa[xh[j]]=xh[i],tj(xh[i],xh[j]),++tt;
	}
	if(tt!=n-1){printf("-1");return 0;}
	dfs(rt);
	for(int i=1;i<=N;i++)
	{
		int tt=0;
		for(int j=i;j<=N;j+=i)if(xh[j]&&(fa[xh[j]]==0||a[fa[xh[j]]]%i!=0))++tt;
		if(tt>1){printf("-1");return 0;}
	}
	for(int i=1;i<=n;i++)printf("%d ",fa[i]);
}