hihoCoder 数组重排

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

找每个位置循环节的大小。

得到结果d1, d2, ....., dn。

最终结果cmd(d1, d2, ...., dn)。

水题。

题目链接：

http://hihocoder.com/contest/hihointerview11/problem/1

代码：

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn =  + ;

 typedef long long int64;

 int n;

 int p[maxn];

 int64 cal(int a){

       int t = p[a], cnt = ;

       while(t != a){

             t = p[t];

             cnt++;

       }

       return (int64)cnt;

 }

 int64 gcd(int64 a, int64 b){

       if( b ==  )

             return a;

       return gcd(b, a%b);

 }

 int main(void){

       scanf("%d", &n);

       for(int i = ; i <= n; ++i){

             scanf("%d", &p[i]);

       }

       int64 a = cal();

       int64 ans = a;

       for(int i = ; i <= n; ++i){

            int64 b = cal(i);

            ans = ans * b / gcd(ans, b);

       }

       printf("%d\n", (int)ans);

       return ;

 }