P2582

云浅知处 · 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;
}