号称是置换群的题目。。没看出来哪里像NOIP05年第三题了，这就是所谓的置换群？
顺着枚举 找到1-a-b-c-...-1的一个序列 将这个序列作为一个基元素，那么整个集合每调动一次，基元素就顺时针旋转一格，可知，一个长度为a的序列旋转a次即还原，那么所有的基元素都还原的时候可知整个序列到达初始值。问题就演变成了求每个基元素长度的最小公倍数。
#include<stdio.h>
long n,i,top,w,z;
long f[1001],ans[1001],bj[1001];
long gcd(long a,long b)
{
if (b==0)
return a;
else if (b==1)
return 1;
if (a<b)
return gcd(b,a);
return gcd(a%b,b);
}
long g(long a,long b)
{
__int64 x,y;
x=a;y=b;x*=y;
z=gcd(a,b);
x/=z;
z=x;
return z;
}
long visit(long i)
{
long ans;
ans=0;
while (bj[i]==0)
{
bj[i]=1;
ans++;
i=f[i];
}
return ans;
}
int main()
{
scanf("%ld",&n);
for (i=1;i<=n;i++)
scanf("%ld",&f[i]);
for (i=1;i<=n;i++)
{
if (bj[i]==0)
{
top++;
ans[top]=visit(i);
}
}
w=ans[1];
for (i=2;i<=top;i++)
w=g(w,ans[i]);
printf("%ld",w);
}
posted on 2011-07-05 22:28
梦转千寻 阅读(79)
评论(0) 编辑 收藏 引用