题目回顾

给定一个长度为 $n$ 的排列 $p$，构造一个长度为 $n$ 的排列 $q$，满足： 对所有 $1 \le i < n$，有

核心解法

构造方案

直接令：

这个构造方式可以完美满足题目所有要求，且实现简单。

严谨证明

1. 证明 $q$ 是一个合法排列

排列的定义：数组包含 $1 \sim n$ 的所有整数，无重复、无遗漏。

1. 由构造公式得：$$p_i + q_i = n+1$$
2. 已知 $p$ 是 $1 \sim n$ 的排列，即 $p_i \in [1,n]$，因此：$$q_i = n+1-p_i \in [1,n]$$
3. 因为 $p$ 中所有元素互不相同，所以 $q_i = n+1-p_i$ 也互不相同。

综上，$q$ 是 $1 \sim n$ 的合法排列。

2. 证明相邻和的 $\gcd \ge 3$

1. 根据构造公式：$$p_i+q_i = n+1$$ $$p_{i+1}+q_{i+1} = n+1$$
2. 两个相等的数的最大公约数等于它本身：$$\gcd(n+1,\ n+1) = n+1$$
3. 题目约束 $n \ge 2$，因此：$$n+1 \ge 3$$

最终可得：

完全满足题目要求。

代码实现（C++）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 加速输入输出，应对大数据范围
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            // 核心构造公式
            cout << n + 1 - x << " ";
        }
        cout << "\n";
    }
    return 0;
}

代码说明

1. 输入优化：ios::sync_with_stdio(false); cin.tie(nullptr); 用于处理题目大数据量（$n \le 2 \times 10^5$）；
2. 核心逻辑：对每个输入的 $p_i$，直接计算 $n+1-p_i$ 并输出，就是答案排列 $q$；
3. 效率：时间复杂度 $O(n)$，空间复杂度 $O(1)$，完全符合题目限制。

样例验证

以第一个样例为例： $n=3,\ p=[1,3,2]$ $q_1=3+1-1=3$？不影响正确性，题目允许任意合法解） 核心结论：所有相邻和都等于 $n+1$，$\gcd$ 必然满足条件。

总结

1. 构造公式：$\boldsymbol{q_i = n+1-p_i}$；
2. 该公式保证 $q$ 是排列，且所有相邻和相等，$\gcd = n+1 \ge 3$；
3. 代码极简，时间/空间效率最优，可直接通过所有测试用例。