自动搬运

查看原文

来自洛谷，原作者为

	云浅知处 喵

搬运于2025-08-24 21:39:19，当前版本为作者最后更新于2021-08-24 09:40:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

很好的一道题。感觉评蓝有点低了。

首先注意到一个性质：如果 $g(x)=k$，那么就有：

以此类推，我们可以推出：对任意的 $m$，均有：

也就是说，如果我们将每个 $i$ 和 $f(i)$ 看做一条有向边 $i\to f(i)$，那么：左边相当于在 $x$ 所在的环上走 $m$ 步，右边相当于在 $k$ 所在的环上走 $m$ 步。

方便起见，我们设建图之后点 $i$ 所在环的大小为 $\text{Size}(i)$。

这样一来，如果 $g(x)=k$，那么，由于对任意的 $m$，两边在各自的环上走 $m$ 步后的值都要相等，就必须有：

即 $\text{Size}(k)$ 为 $\text{Size}(x)$ 的约数。否则，当 $m=\text{Size}(x)$ 时，已经出现了矛盾。

那么，我们首先建图，对每个点求出它的 $\text{Size}(x)$，然后枚举约数计算即可。时间复杂度为 $O(n+\sum\sqrt{\text{Size}(i)})=O(n)$。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>

const int MN=8e5+5;

using namespace std;

int n,f[MN],g[MN];
bool vis[MN];
int mn[MN],s[MN];

int dfs(int x){
    if(vis[x])return 0;
    vis[x]=1;
    return dfs(f[x])+1;
}

void dfs2(int x,int sz){
    if(vis[x])return ;
    vis[x]=1,s[x]=sz;
    dfs2(f[x],sz);
}

void dfs3(int x,int y){
    if(vis[x])return ;
    vis[x]=1,g[x]=y;
    dfs3(f[x],f[y]);
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>f[i];

    for(int i=1;i<=n;i++){
        if(!vis[i]){
            s[i]=dfs(i);
            if(!mn[s[i]])mn[s[i]]=i;
        }
    }

    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)if(!vis[i])dfs2(i,s[i]);
    
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            int Mn=1000000;
            for(int j=1;j*j<=s[i];j++){
                if(s[i]%j==0){
                    if(mn[j]>0)Mn=min(Mn,mn[j]);
                    if(mn[s[i]/j]>0)Mn=min(Mn,mn[s[i]/j]);
                }
            }
            dfs3(i,Mn);
        }
    }

    for(int i=1;i<=n;i++)cout<<g[i]<<" ";puts("");
    return 0;
}