http://acm.timus.ru/problem.aspx?space=1&num=1024
找出所有的循环，计算循环长度的最小公倍数
1 #include <iostream>
2 using namespace std;
3 int n;
4 int p[1001];
5 bool v[1001];
6 long long int an,alist[1001];
7 int vnum;
8 int mm;
9
10 long long int gcd(long long int a,long long int b){
11 if (b==0) return a;
12 else return gcd(b,a%b);
13 }
14
15 void calc(int x){
16 int deep=0;
17 while (!v[x]){
18 v[x]=true;
19 x=p[x];
20 ++deep;
21 }
22 alist[++an]=deep;
23 if (deep>mm) mm=deep;
24 }
25
26 int main(){
27 scanf("%d",&n);
28 vnum=n;
29 for (int i=1;i<=n;++i) scanf("%d",&p[i]);
30 for (int i=1;i<=n;++i) if (!v[i]) calc(i);
31 long long int ans=mm;
32 for (int i=1;i<=an;++i) ans=(long long)ans*(long long)alist[i]/(long long)gcd(ans,alist[i]);
33 cout<<ans;
34 }
35
posted on 2008-11-04 11:23
Joseph 阅读(332)
评论(2) 编辑 收藏 引用