4278. [THUPC 2025 Final] 排列与质数

【题目描述】

给定正整数 $n$，构造一个 $1$ 至 $n$ 的排列 $p_1,p_2,\dots,p_n$ 满足以下条件：

• 对于 $1 \le i \le n$，设 $c_i = \left\lceil \frac{p_1+p_2+\dots +p_i}{i} \right\rceil$，则在 $c_1,c_2,\dots,c_n$ 中至少有 $\left\lfloor \frac{n}{3} \right\rfloor - 1$ 个质数。

【输入格式】

本题有多组测试数据。输入的第一行一个整数 $t\ (1 \le t \le 10)$ 表示测试数据组数，接下来依次描述每组测试数据。

每组测试数据输入一行一个整数 $n\ (2 \le n \le 10 ^ 5)$。

【输出格式】

对于每组数据输出满足题设条件的任意一个排列 $p_1,p_2,\dots,p_n$。保证这样的排列存在。

【输入样例】

2
2
3

【输出格式】

2 1
2 1 3

【样例解释】

对于第一组测试数据，我们有 $c_1 = \left\lceil \frac{2}{1} \right\rceil = 2$ 和 $c_2 = \left\lceil \frac{2+1}{2} \right\rceil = 2$。两个都是质数。

对于第二组测试数据，$c_1 = c_2 = c_3 = 2$。

【来源】

清华大学学生算法协会 GitLink 仓库