题目回顾

要求构造一个长度为 $n$ 的排列 $p$，使得任意相邻两项 $p_i + p_{i+1}$ 是合数。若不可能，输出 $-1$。

关键思路

$1$. 同奇偶性相加为偶数

• 所有大于 $2$ 的偶数都是合数。
• 偶数 $+$ 偶数 $=$ 偶数（且大于 $2$ 时一定是合数）。
• 奇数 $+$ 奇数 $=$ 偶数（且大于 $2$ 时一定是合数）。

因此，只要相邻两数同为奇数或同为偶数，它们的和一定是偶数且大于 $2$，所以一定是合数。

$2$. 奇偶交替的问题

如果排列中相邻两数一个是奇数、一个是偶数，那么和为奇数，可能是素数也可能是合数。我们需要避免出现和为素数的情况。

所以，我们可以尝试将排列分成两段：

• 所有偶数放在一起（相邻的偶数相加是合数）
• 所有奇数放在一起（相邻的奇数相加是合数）

这样，中间只存在一个“奇偶交界”的位置，即偶数的最后一个与奇数的第一个相邻（或反过来）。我们只需要保证这个跨奇偶的和也是合数。

$3$. 寻找合适的交界数对

我们只需要找到一对奇数和一个偶数，使得它们的和为合数。

已知最小的奇数是 $1, 3, 5, \dots$，最小的偶数是 $2, 4, 6, \dots$。

• $1 + 2 = 3$（素数，不行）
• $1 + 4 = 5$（素数，不行）
• $3 + 2 = 5$（素数，不行）
• $3 + 4 = 7$（素数，不行）
• $5 + 4 = 9$（合数，可行）

因此，在 $n \ge 5$ 时，我们可以使用 $4$（偶数）和 $5$（奇数）作为交界数对。

$4$. 构造方法

步骤：

$1$. 先输出所有偶数（除了 $4$ 暂时保留），顺序任意，比如从小到大：

$2$. 然后输出 $4$ 和 $5$：

$3$. 最后输出所有奇数（除了 $5$），顺序任意，比如从小到大：

这样：

• 偶数段内部相邻和是偶数且大于 $2$ → 合数。
• 奇数段内部相邻和是偶数且大于 $2$ → 合数。
• 偶数段最后一个与 $4$ 的和？
  偶数段最后一个可能是某个偶数 $e$，$e + 4$ 是偶数且大于 $2$ → 合数。
• $4 + 5 = 9$ → 合数。
• $5 +$ 奇数段第一个（$1$ 或 $3$ 或 $7$ 等）
  注意：奇数段第一个可能是 $1$，$5 + 1 = 6$（合数）；
  如果 $1$ 已经用过，则下一个是 $3$，$5 + 3 = 8$（合数）；
  如果 $3$ 也用过（$n=5$ 时只有 $1,3,5$ 奇数），则 $5+3=8$ 仍为合数。
  实际上，$5$ 加任何奇数（除了 $5$ 自身）结果都是偶数且大于 $2$，所以一定合数。

$5$. 小 $n$ 的情况

• $n = 2$：排列 $(1,2)$，$1+2=3$ 素数，不行；$(2,1)$ 同样。无解。
• $n = 3$：所有排列都会出现奇偶相邻且和为素数的情况（经暴力验证），无解。
• $n = 4$：所有排列都会出现奇偶相邻且和为素数的情况，无解。
• $n = 5$：有解，如上构造：$$2, 4, 5, 1, 3$$ 检验： $2+4=6$（合数），$4+5=9$（合数），$5+1=6$（合数），$1+3=4$（合数）。

代码实现（C++）

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        if (n < 5) {
            cout << -1 << endl;
            continue;
        }
        
        // 输出偶数（除了4）
        for (int i = 2; i <= n; i += 2) {
            if (i != 4) {
                cout << i << " ";
            }
        }
        
        // 输出4和5作为交界
        cout << "4 5 ";
        
        // 输出奇数（除了5）
        for (int i = 1; i <= n; i += 2) {
            if (i != 5) {
                cout << i << " ";
            }
        }
        
        cout << endl;
    }
    
    return 0;
}

总结

• 利用同奇偶相加得偶数的性质，将奇数和偶数各自放在连续段中。
• 唯一需要处理的是奇偶交界处，找到一个偶数和一个奇数相加为合数。
• 最小可行对是 $(4, 5)$，因此 $n \ge 5$ 时可行，$n \le 4$ 时无解。
• 构造顺序为：除$4$外的偶数 → $4$ $5$ → 除$5$外的奇数。