因为题目的编号是2^10，所以决定写一下题解。

题目大意：给出一个n阶的置换P，问P的多少次幂等于单位元E。n <= 1000，保证答案不超过1e9.

如果有一点置换群的知识的话就很好解决了，其实题目也就清楚的告诉你是怎么置换了。我们知道在置换群中有这样一个定理

  • 任何一个置换都可以表示成若干循环的乘积

关于循环的概念，相信应该不难理解，简单点说就是根据题目，_P_k(x) ＝ x，__则在置换过程中得到的k个数便构成一个k阶的循环。题目要求的答案便是k1, k2…..kn的最小公倍数。显然，对于1～n，每个数字仅会出现在一个循环当中，同一个循环中的数对于的k便是一样的。这样复杂度就可以做到O(nlogn)，由于n只有1000，我就懒得去标记什么的了，直接用O(n^2 logn)的做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>

using namespace std;

int f[1010] = {0};

int gcd(int a, int b) {
    return (b == 0) ? a : gcd(b, a%b);
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> f[i];
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        int x = f[i], loop = 1;
        while (x != i) {
            x = f[x];
            loop++;
        }
        ans = ans * (loop / gcd(ans, loop));
    }
    cout << ans << endl;
    return 0;
}

期间WA过一次，原因是这个

  • ans = ans * (loop / gcd(ans, loop));

写成这样子

  • ans = ans * loop / gcd(ans, loop);

但是没用long long 结果就乘爆了，使用上面的式子并用int，以及时候下面的式子并使用long long，后者在时间以及空间上十分微妙的更优一些，这是为什么呢，因为括号的缘故？求科普啊。