← 返回题目列表

Codeforces · 2123/F

F. 最小化固定点

中文机器翻译题面 查看原题

调用长度为 $$$n$$$ 的排列$$$^{\text{∗}}$$$ $$$p$$$ 好 如果 $$$\gcd(p_i, i)$$$$$$^{\text{†}}$$$ $$$\gt 1$$$ 对于所有 $$$2 \leq i \leq n$$$。找到一个好的排列 最小值 数量 固定点$$$^{\text{‡}}$$$ 涵盖长度 $$$n$$$ 的所有良好排列。如果有多个这样的排列,则打印其中任何一个。

$$$^{\text{*}}$$$ 长度 $$$n$$$ 的排列是一个数组,其中包含从 $$$1$$$ 到 $$$n$$$ 的每个整数,且顺序任意。

$$$^{\text{†}}$$$$$$\gcd(x, y)$$$ 表示 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

$$$^{\text{‡}}$$$A 定点 排列 $$$p$$$ 的 是索引 $$$j$$$ ($$$1\leq j\leq n$$$),使得 $$$p_j = j$$$。

输入

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

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

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

输出

对于每个测试用例,在单行上输出长度 $$$n$$$ 的良好排列示例,其中固定点数量最少。

示例

输入
复制

4
2
3
6
13

输出
复制

1 2
1 2 3
1 4 6 2 5 3
1 12 9 6 10 8 7 4 3 5 11 2 13

注意

在第三个样本中,我们构建了排列

$$$i$$$$$$p_i$$$$$$\gcd(p_i, i)$$$
$$$1$$$$$$1$$$$$$1$$$
$$$2$$$$$$4$$$$$$2$$$
$$$3$$$$$$6$$$$$$3$$$
$$$4$$$$$$2$$$$$$2$$$
$$$5$$$$$$5$$$$$$5$$$
$$$6$$$$$$3$$$$$$3$$$
然后我们看到 $$$\gcd(p_i, i) \gt 1$$$ 对于所有 $$$2\leq i\leq 6$$$。此外,我们看到只有两个不动点,即 $$$1$$$ 和 $$$5$$$。可以证明,用较少的固定点构建长度 $$$6$$$ 的良好排列是不可能的。