A16550. Anisphia Wynn Palettia and Good Permutations
编程题
普及+/提高
知识点
题目描述
我一直很喜欢“魔法”这个词。它能让人快乐，让人露出微笑。
——Anisphia Wynn Palettia
Anis 和她的新助手 Euphie 正在改进女巫的扫帚！魔法学需要极高的精度和谨慎——为了让扫帚飞起来，扫帚的构造中必须尽可能少有瑕疵。
对于任意长度为 $m$ 的数组 $a$，如果存在 $i$（$1 \leq i \leq m-2$），使得 $a_i$、$a_{i+1}$ 和 $a_{i+2}$ 互质（两两互质），则称下标 $i$ 是坏下标。更正式地说，当且仅当 $\gcd(a_i,a_{i+1}) = \gcd(a_i,a_{i+2}) = \gcd(a_{i+1},a_{i+2}) = 1$ 时，$i$ 是坏下标。此外，如果一个数组 $a$ 的坏下标不超过 $6$ 个，则称 $a$ 是好数组。
现在给定一个整数 $n$，请构造一个长度为 $n$ 的好排列 $p$。可以证明一定存在这样的排列。
注意，你无需最小化坏下标的个数。
$\gcd(x, y)$ 表示 $x$ 与 $y$ 的最大公约数。
排列定义为从 $1$ 到 $n$ 的所有整数恰好出现一次且顺序可以任意的数组。
——Anisphia Wynn Palettia
Anis 和她的新助手 Euphie 正在改进女巫的扫帚！魔法学需要极高的精度和谨慎——为了让扫帚飞起来，扫帚的构造中必须尽可能少有瑕疵。
对于任意长度为 $m$ 的数组 $a$，如果存在 $i$（$1 \leq i \leq m-2$），使得 $a_i$、$a_{i+1}$ 和 $a_{i+2}$ 互质（两两互质），则称下标 $i$ 是坏下标。更正式地说，当且仅当 $\gcd(a_i,a_{i+1}) = \gcd(a_i,a_{i+2}) = \gcd(a_{i+1},a_{i+2}) = 1$ 时，$i$ 是坏下标。此外，如果一个数组 $a$ 的坏下标不超过 $6$ 个，则称 $a$ 是好数组。
现在给定一个整数 $n$，请构造一个长度为 $n$ 的好排列 $p$。可以证明一定存在这样的排列。
注意，你无需最小化坏下标的个数。
$\gcd(x, y)$ 表示 $x$ 与 $y$ 的最大公约数。
排列定义为从 $1$ 到 $n$ 的所有整数恰好出现一次且顺序可以任意的数组。
输入格式
第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例数量。
每个测试用例占一行，包含一个整数 $n$（$3 \leq n \leq 2 \cdot 10^5$）。
保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。
每个测试用例占一行，包含一个整数 $n$（$3 \leq n \leq 2 \cdot 10^5$）。
保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。
输出格式
对每个测试用例，输出一行 $n$ 个整数 $p_1, p_2, \ldots, p_n$，表示一个长度为 $n$ 的好排列。若有多个解，可输出任意一个。
输入输出样例
输入 #1
4 3 6 8 9
输出 #1
2 1 3 4 1 6 3 5 2 4 1 6 3 5 2 8 7 5 4 8 1 9 3 6 2 7
说明/提示
对于 $n=9$，例如：
| $i$ | $p_i$ | $p_{i+1}$ | $p_{i+2}$ | $\gcd(p_i, p_{i+1})$ | $\gcd(p_i, p_{i+2})$ | $\gcd(p_{i+1}, p_{i+2})$ |
| --- | --- | --- | --- | --- | --- | --- |
| $1$ | $5$ | $4$ | $8$ | $1$ | $1$ | $4$ |
| $2$ | $4$ | $8$ | $1$ | $4$ | $1$ | $1$ |
| $3$ | $8$ | $1$ | $9$ | $1$ | $1$ | $1$ |
| $4$ | $1$ | $9$ | $3$ | $1$ | $1$ | $3$ |
| $5$ | $9$ | $3$ | $6$ | $3$ | $3$ | $3$ |
| $6$ | $3$ | $6$ | $2$ | $3$ | $1$ | $2$ |
| $7$ | $6$ | $2$ | $7$ | $2$ | $1$ | $1$ |
唯一的坏下标是 $3$。因为 $1 \leq 6$，所以 $p$ 是一个好排列。
| $i$ | $p_i$ | $p_{i+1}$ | $p_{i+2}$ | $\gcd(p_i, p_{i+1})$ | $\gcd(p_i, p_{i+2})$ | $\gcd(p_{i+1}, p_{i+2})$ |
| --- | --- | --- | --- | --- | --- | --- |
| $1$ | $5$ | $4$ | $8$ | $1$ | $1$ | $4$ |
| $2$ | $4$ | $8$ | $1$ | $4$ | $1$ | $1$ |
| $3$ | $8$ | $1$ | $9$ | $1$ | $1$ | $1$ |
| $4$ | $1$ | $9$ | $3$ | $1$ | $1$ | $3$ |
| $5$ | $9$ | $3$ | $6$ | $3$ | $3$ | $3$ |
| $6$ | $3$ | $6$ | $2$ | $3$ | $1$ | $2$ |
| $7$ | $6$ | $2$ | $7$ | $2$ | $1$ | $1$ |
唯一的坏下标是 $3$。因为 $1 \leq 6$，所以 $p$ 是一个好排列。