题意:输入长度为n(1 <= n <= 1000)的置换，定义P(n) = P1(n), Pk(n) = P(Pk-1(n));问K为多少时，置换之后变成f[i] = i的置换；
水题:用的就是循环相乘，元素对应关系的理解；即(a1,a2,a3...,an)经过一次相乘之后，a1->a3(a1->a2->a3);所以对于每个循环，要使得a1->a1,该循环K的值就是循环的大小；所以直接求出所有循环大小的lcm即可；
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> #include<map> #include<queue> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef __int64 ll; template<typename T> void read1(T &m) { T x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+‘0‘); } int a[1010]; int __gcd(int a,int b) { return b == 0?a:__gcd(b,a%b); } int lcm(int a,int b) { return a/__gcd(a,b)*b; } int vis[1010],B[1010]; int main() { int N; read1(N); rep1(i,1,N) read1(B[i]); int ans = 1; rep1(i,1,N){ int tmp = i,cnt = 0; do{ vis[tmp] = ++cnt; tmp = B[tmp]; }while(!vis[tmp]); ans = lcm(ans,cnt); } printf("%d\n",ans); return 0; }
原文：http://www.cnblogs.com/hxer/p/5222945.html
