洛谷 P2582 函数

函数 - 洛谷

可以发现性质 \(g(f^m(x))=f^m(g(x))\) 。

若设左侧 \(x\) 所在环大小为 \(size(x)\) ，右侧 \(g(x)\) 所在环的大小为 \(size(gx)\) 。

可以得到，\(size(gx)\mid size(x)\) 。

这是因为左侧下标呈循环，右侧的值呈循环，若环的大小不满足 \(size(gx)\mid size(x)\) ，必然会出现矛盾。

于是我们首先 \(O(n)\) 求出每个环的大小，枚举约数计算最小满足条件的 \(g(x)\) 即可，然后后面的数就可以迭代填出。

#include <bits/stdc++.h>
const int Maxn = 8e5 + 5;
int n, f[Maxn], g[Maxn], sz[Maxn], num[Maxn];
bool vis[Maxn];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &f[i]);
    for (int i = 1; i <= n; i++)
    {
        if (vis[i]) continue;
        int x = i, cnt = 0;
        do {x = f[x], ++cnt;} while(x != i);
        do {x = f[x]; sz[x] = cnt; vis[x] = true;} while(x != i);
        if (!num[cnt]) num[cnt] = x;
    }
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++)
    {
        if (vis[i]) continue;
        int sav = 0x3f3f3f3f;
        for (int j = 1; j * j <= sz[i]; j++)
        {
            if (sz[i] % j == 0)
            {
                if (num[j]) sav = std::min(sav, num[j]);
                if (j * j != sz[i] && num[sz[i] / j])
                    sav = std::min(sav, num[sz[i] / j]);
            }
        }
        int x = i;
        do {g[x] = sav, vis[x] = true, x = f[x], sav = f[sav]; } while(x != i);
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", g[i]);
    return 0;
}