传送门：https://codeforces.com/problemset/problem/542/C
我们把序列的映射关系看作\(i\rightarrow f(i)\)的边，要使\(f(f(i))=f(i)\)，显然存在\(i\)点距离不超过\(1\)的长度为\(1\)的自环。
推广到\(f^{(k)}(x)\)满足题意则会在距离\(x\)点距离不超过\(k\)的长度为\(k\)的环。我们要使\(f^{(k)}(x)=f^{(k)}(\ f^{(k)}(x))\)，成立，当前仅当存在一个长度为\(z\)的环，与$\ x\ \(联通且距离不超过\)k\(。且\)k|z\(（因为需要绕一圈回到原点）。我们要使此关系对于任意\)x\(成立，则最小\)k\(为所有环长度的最小公倍数，若\)k\(小于所有点与最近环的距离，则需要将答案倍乘到\)≥$此距离。
可以\(O(n)\)预处理所有环以及每个点与环的距离，具体见以下答案。总时间复杂度\(O(nlog_2{n})\)，瓶颈在于最大公约数。
#include <bits/stdc++.h>#define int long long
using namespace std;inline int read() {char c;bool flag = false;while ((c = getchar()) < '0' || c > '9') if (c == '-') flag = true;int res = c - '0';while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';return flag ? -res : res;
}const int N = 201;struct Edge {int v, next;
} e[N];int head[N], cnt;void add(int u, int v) {e[cnt].v = v;e[cnt].next = head[u];head[u] = cnt++;
}int dis[N], c, b, flag, len[N], vis[N], v;void dfs(int x) {if (vis[x] && vis[x] != v) return;if (vis[x] && vis[x] == v) {b = x;flag = 1;++c;return;}vis[x] = v;for (int i = head[x]; ~i; i = e[i].next) dfs(e[i].v);if (x != b && flag) ++len[c];if (x == b) {++len[c], flag = 0, b = 0;return;}if (!flag) dis[x] = dis[e[head[x]].v] + 1;
}int gcd(int aa, int bb) { return bb ? gcd(bb, aa % bb) : aa; }signed main() {memset(head, -1, sizeof head);int n = read();for (int i = 1; i <= n; ++i) {int u = read();add(i, u);}for (int i = 1; i <= n; ++i) if (!vis[i]) ++v, dfs(i);int mx = 0;for (int i = 1; i <= n; ++i) mx = max(mx, dis[i]);int ans = len[1];for (int i = 2; i <= c; ++i) ans = ans / gcd(ans, len[i]) * len[i];if (mx > ans) printf("%lld", mx % ans ? ans * (mx / ans + 1) : mx);else printf("%lld", ans);return 0;
}
