Rating 900

2137B 有趣的数列

来源：CodeForces Round 1047 (Div. 3)-B. Fun Permutation

Tags: 构造算法 数学 数论

中文题面可在本博客的cf题单中查看: 本题链接

根据题目可知，给定一个大小为 $n$ 的排列 $p$。找到一个大小为 $n$ 的排列 $q$,使得对于所有 $1 \leq i<n$,满足 $\operatorname{GCD}$ $(p_i+q_i, p_{i+1}+q_{i+1}) \geq 3$。

那么，我们假设存在一个大小为 $n$ 的排列 $q$。使得 $\operatorname{GCD}$ $(p_i+q_i, p_{i+1}+q_{i+1}) \geq 3$

由输入的 $n$ 的范围可知，$\forall n \geq 2$ 。于是，我们尝试构建一个数列 $q$ ，使得 $q$ 的元素与 $p$ 的元素之和的 $\operatorname{GCD}$ 值等于 $n+1$ $^{\text{∗Tip:}} \operatorname{GCD}(n+1,n+1)=n+1\geq 3$。又因为数列 $p$ 是一个排列，所以 $q$ 也是一个排列，于是有 $p_i+q_i=n+1$ ,所以 $q_i=n-p_i+1$ 。

所以题解为:

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

void solve() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    for (ll i=0;i<n;i++) {
        cin>>a[i];
        if (i>0) cout<<" ";
        cout<<n-a[i]+1;
    }
    cout<<endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll t;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}