1 题目大意
1.1 题目翻译：
给定一个值域为 \([1,n]\) 的函数 \(f(x)\)，让你求出最小的 \(k\)，其中 \(k\) 满足 \(f^{(2k)}(x) = f^{(k)}(x)\)。
其实我觉得这题你谷翻译十分到位，建议没读懂题的还是去看你谷翻译罢。
1.2 数据范围：
对于 \(100\%\) 的数据：
- \(1 \leq n \leq 200\)
1.3 *关于数据范围
这个 \(n\) 其实可以开到 \(2 \times 10^5\) 的，但前提是你得加一个高精度。出题人好仁慈，拜谢出题人。
2 解法分析
发现出现了 \(f^{k}(x)\) 这种东西，不难想到建图。
我们可以把 \(x\) 向 \(a_x\) 连一条有向边。不难发现，整个图被分成了多个连通块，每一个连通块都形似基环树。我们可以把每一个环的大小和一个点到环的最短距离算出来。
现在，我们分两种情况讨论。设答案为 \(k\)：
-
如果结点 \(u\) 在环中，设这个环大小为 \(s\)，那么这个结点必须绕至少 \(s\) 次才能出现相等。所以，\(s \ | \ k\)。
-
如果结点 \(u\) 不在环上，设这个结点到环的最短距离为 \(d\)，那么这个结点只有走至少 \(d\) 次才能到环。所以，\(k \geq d\)。
于是，答案就简单了。我们把所有环的大小取最小公倍数 \(\operatorname{lcm}\)，然后算出第二种结点 \(d\) 的最大值 \(p\)。如果 \(p \leq \operatorname{lcm}\)，那么就成立；否则，还要用带余除法计算出最小的 \(w\)，满足 \(w \cdot \operatorname{lcm} >= p\)。此时，\(w \cdot \operatorname{lcm}\) 即为答案。
3 AC Code
代码丑的要死，将就着看吧。
int dfs(int x) {
if (vis[x])
return dis[x];
vis[x] = 1;
dfn[x] = ++ timetmp;
int num = dfs(a[x]);
if (vis[a[x]] == 1)
p = a[x], num = dfn[x] - dfn[p] + 1;
else if (cycle[a[x]] == 1) dis[x] = 1;
else dis[x] = num + 1;
if (p > 0 && vis[p] == 1)
cycle[x] = 1, dis[x] = num;
vis[x] = 2;
return dis[x];
}
void solve() {
cin >> n;
f (i, 1, n)
scanf("%lld", &a[i]);
int k = 1;
f (i, 1, n)
if (!vis[i]) {
p = -1;
dfs(i);
}
f (i, 1, n)
if (cycle[i])
k = k * dis[i] / __gcd(k, dis[i]);
int x = 0;
f (i, 1, n)
if (!cycle[i])
x = max(x, dis[i]);
if (x > k)
k = ((x - 1) / k + 1) * k;
printf("%lld\n", k);
}