F. Minimize Fixed Points

Codeforces 第 1034 轮 (Div. 3) F

问题

如果一个长度为 $n$ 的排列 $p$ 对于所有 $2 \le i \le n$ 都满足 $\gcd(p_i, i) > 1$，则称其为 好 排列。在所有长度为 $n$ 的好排列中，找到一个具有 最少 不动点 的排列。如果存在多个这样的排列，输出任意一个即可。

• 一个长度为 $n$ 的 排列 是一个包含从 $1$ 到 $n$ 的每个整数恰好一次的数组，顺序不限。
• $\gcd(x, y)$ 表示 $x$ 和 $y$ 的 最大公约数 (GCD)。
• 一个排列 $p$ 的 不动点 是一个索引 $j$ ($1 \le j \le n$)，使得 $p_j = j$。

输入

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) — 测试用例的数量。

每个测试用例的唯一一行包含一个整数 $n$ ($2 \le n \le 10^5$) — 排列的长度。

保证所有测试用例的 $n$ 的总和不超过 $10^5$。

输出

对于每个测试用例，输出一行，给出一个长度为 $n$ 且具有最少不动点的好排列的例子。

题解

思路

首先将排列初始化为单位排列，即对于所有 $i$，$p_i = i$。然后，尝试修改它以满足条件。

为了实现这一点，对于每个 $i$，将 $p_i$ 与 $p_{spf(i)}$ 交换，其中 $spf(i)$ 是 $i$ 的最小质因数。例如，如果 $i = 6$，最小质因数是 $2$，所以交换 $p_6$ 和 $p_2$。这确保了 $\gcd(p_6, 6) \ge 2$，并有助于减少不动点的数量。不动点的数量将减少到与排列中所有其他元素互质的元素的数量。

提交链接