CF542C题解

传送门：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;
}