题目描述

给你一个偶数 n，已知存在一个长度为 n 的排列 perm，其中 perm[i] == i（下标 从 0 开始 计数）。

一步操作中，你将创建一个新数组 arr，对于每个 i：

• 如果 i % 2 == 0，那么 arr[i] = perm[i / 2]
• 如果 i % 2 == 1，那么 arr[i] = perm[n / 2 + (i - 1) / 2]

然后将 arr 赋值给 perm。

要想使 perm 回到排列初始值，至少需要执行多少步操作？返回最小的 非零 操作步数。

样例

输入：n = 2
输出：1
解释：最初，perm = [0,1]
第 1 步操作后，perm = [0,1]
所以，仅需执行 1 步操作

输入：n = 4
输出：2
解释：最初，perm = [0,1,2,3]
第 1 步操作后，perm = [0,2,1,3]
第 2 步操作后，perm = [0,1,2,3]
所以，仅需执行 2 步操作

输入：n = 6
输出：4

限制

• 2 <= n <= 1000
• n 是一个偶数。

算法

(数学) $O(n)$

1. 数字 0 和 n-1 的位置是不会变化的。位置 $i \in [1, n - 1]$ 上的数字下一次会变到位置 $f(i)$ 上，其中
   • $i < n / 2$ 时，$f(i) = 2i$;
   • $i \ge n / 2$ 时，$f(i) = 2i - (n - 1)$
2. 综合来看，$f(i) = 2i \text{ mod } (n - 1)$，对于任意的 $i \in [1, n - 1]$ 都成立。
3. 需要找到最小的 $k > 0$，使得对于任意的 $i \in [1, n - 1]$，都有 $2^k \cdot i \equiv i \text{ mod } (n - 1)$，即 $(2^k - 1)i \equiv 0 \text{ mod } (n - 1)$。
4. 当 $i = 1$ 时，需要解 $2^k - 1 \equiv 0 \text { mod } (n - 1)$ 的最小的 $k$。同时，这个解也适用于其他 $i > 1$ 的情况。换句话说，$i = 1$ 是条件最严格的，解出 $i = 1$ 情况下的最小的 $k$ 就可以。
5. 根据欧拉定理，可知 $2^{\phi(n-1)} \equiv 1 \text{ mod } (n - 1)$，其中 $\phi(n - 1)$ 为不超过 $n - 1$ 且与 $n - 1$ 互质的正整数的个数，是方程的一个特解（不一定是最小解），所以暴力枚举 $k$ 即可在 $O(n)$ 的时间复杂度下求解。

时间复杂度

• 暴力枚举的时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int reinitializePermutation(int n) {
        if (n == 2) return 1;
        int k = 1;
        for (int p = 2; p != 1; p = p * 2 % (n - 1), k++);
        return k;
    }
};