3090734_ac_1606ms_3316k.java

来自「北大大牛代码 1240道题的原代码 超级权威」· Java 代码 · 共 41 行

import java.util.*;

public class Main
{
	public static void main(String[] args)
	{
		Scanner cin = new Scanner(System.in);
		int i, j, n;
                int [] a = new int [1001];
                boolean [] v = new boolean [1001];
                
		n = cin.nextInt();
                for(i = 1; i <= n; i++)
                {
                    a[i] = cin.nextInt();
                }
                int ans = 1;
                for(i = 1; i <= n; i++)
                {
                    if(v[i])
                    {
                        continue;
                    }
                    int cnt = 0;
                    j = i;
                    do
                    {
                        cnt++;
                        v[j] = true;
                        j = a[j];
                    }while(j!=i);
                    ans = ans*cnt/gcd(ans,cnt);
                }
                System.out.println(ans);
	}

    private static int gcd(int ans, int cnt) 
    {
        return ans == 0 ? cnt : gcd (cnt%ans,ans);
    }
}