A16550 | $Anisphia Wynn Palettia and Good Permutations$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

我一直很喜欢“魔法”这个词。它能让人快乐，让人露出微笑。 ——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$ 个整数 $p_1, p_2, \ldots, p_n$，表示一个长度为 $n$ 的好排列。若有多个解，可输出任意一个。

输入 #1

输出 #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

C++ 编辑器

输入

输出