题目

题目描述

“Geronimo∼”
时间还很多，让我们慢慢来。
不如听首开心的歌再看题？……算了，直接看题吧
给定一个整数$n$，以及一个$n$阶的排列$p_1,p_2,…,p_n$
我们定义重组过程如下：如果当前的排列是$a_1,a_2,…,a_n$，经过一次重组，就会变成$p_{a_1},p_{a_2},…,p_{a_n}$
问一个排列至少要经过多少次重组才会恢复成重组前的状态
由于答案可能很大，输出其对一个给定的正整数$q$取模的值即可

输入格式

第一行两个正整数$n,q$
第二行一共$n$个整数，依次表示$p_1,p_2,…,p_n$
同一行相邻的数间用一个空格隔开

输出格式

一行一个整数，表示答案对$q$取模的值

样例

样例输入

7 1000000207
2 6 5 1 3 4 7

样例输出

数据范围与提示

对于全部的数据，$q\leqslant 2\times 10^9$
对于$10%$的数据，$q=1$
对于另外$20%$的数据，$n\leqslant 9$
对于另外$40%$的数据，$n\leqslant 10^3$
对于剩下$30%$的数据，$n\leqslant 5\times 10^5$

题解

先求出每一个点要循环几次才能回到原位，然后直接去一个LCM就好了
不能用传统的GCD，因为需要取模！必须用唯一分解定理
附上代码：

#include<algorithm>
#include<cstdio>
using namespace std;
int n,MOD,s,maxs,a[500010],f[500010],sum[500010],p[500010],v[500010];
long long ans=1,P[500010];
int main()
{
    scanf("%d%d",&n,&MOD);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1,x;i<=n;i++){
        if(f[i]) continue;
        x=i;
        for(int j=1;;j++){
            if(sum[x]) break;
            if(!f[x]) f[x]=j;
            else sum[x]=j-f[x];
            x=a[x];
        }
    }
    for(int i=1;i<=n;i++) maxs=max(maxs,sum[i]);
    for(int i=2;i<=maxs;i++){
        if(v[i]) continue;
        p[++s]=i,P[s]=1;
        for(int j=i;j<=maxs;j+=i) v[j]=1;
    }
    sort(sum+1,sum+1+n);
    for(int i=1;i<=n;i++){
        if(sum[i]==sum[i-1]) continue;
        for(int j=1;j<=s;j++){
            long long ppa=1,Sum=sum[i];
            while(Sum%p[j]==0) Sum/=p[j],ppa=ppa*p[j]%MOD;
            P[j]=max(P[j],ppa);
        }
    }
    for(int i=1;i<=s;i++) ans*=P[i],ans%=MOD;
    printf("%lld",ans);
}