描述
题解
根据题意，可以发现，这里一定存在循环节，所以我们先搞定循环节，求所有循环节的LCM即可，有一些细节问题需要格外注意（Two）。
一开始，比较懒，直接暴力枚举解题，然后很自然的TLE了，T了两组数据（One），哎，不得不说，51Nod的数据强度还是很强的。
代码
One：
// TLE
//#include <iostream>
//
//using namespace std;
//
//const int MAXN = 201;
//
//int f[MAXN];
//
//int main(int argc, const char * argv[])
//{
// int n;
// cin >> n;
//
// for (int i = 1; i <= n; i++)
// {
// cin >> f[i];
// }
//
// long long k = 1;
// for (int i = 1; i <= n; i++)
// {
// int res = i;
// for (int j = 0; j < 2 * k; j++)
// {
// res = f[res];
// }
// int tmp = i;
// for (int j = 0; j < k; j++)
// {
// tmp = f[tmp];
// }
// if (res != tmp && i != 1)
// {
// k++;
// i = 0;
// continue;
// }
// if (res == tmp)
// {
// continue;
// }
// while (res != tmp)
// {
// k++;
// tmp = f[tmp];
// res = f[f[res]];
// }
// }
//
// std::cout << k << "\n";
// return 0;
//}Two：
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#define MAXN 201
typedef long long ll;
int f[MAXN];
int m[MAXN];
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b)
{
return a / gcd(a, b) * b;
}
// 找出每个数字进入循环圈的最小值
// k能整除每个数字的循环圈
int main()
{
int n, i, j, next;
ll tmp;
ll ans = 1;
int mink = 1;
scanf("%d", &n);
for (i = 1; i <= n; ++i)
{
scanf("%d", f + i);
}
for (i = 1; i <= n; ++i)
{
memset(m, 0, sizeof(int) * (n + 1));
j = i;
m[f[j]] = 1;
while (true)
{
next = f[j];
if (m[f[next]])
{
tmp = m[f[j]] + 1 - m[f[next]];
if (mink < m[f[next]])
{
mink = m[f[next]];
}
break;
}
m[f[next]] = m[f[j]] + 1;
j = next;
}
ans = lcm(ans, tmp);
}
tmp = ans;
while (ans < mink)
{
ans += tmp;
}
printf("%lld\n", ans);
return 0;
}
京公网安备 11010502036488号