题解 | #小红的排列构造#（数学）

题目解析：

想满足a[i]+i不是质数

我们分奇偶情况

如果是奇数放在奇数位置，加起来一定为偶数

偶数放偶数位置加起来也一定为偶数

偶数必然不是质数（2除外）

因此对于n<3的情况特判一下，其他情况的构造就出来了

#include "bits/stdc++.h"

using namespace std;
#define int long long
#define endl "\n"
#define PII pair<int,int>
#define PIII pair<int,PII>
const int MOD = 1e9 + 7;
const int N = 3e5;

bool cmp(PII p1, PII p2) {
    return p1.first + p1.second < p2.first + p2.second;
}

bool isP(char t1, char t2) {
    int c1 = t1 - '0';
    int c2 = t2 - '0';
    if ((c1 + c2) & 1)return false;
    return true;
}

void slu() {
    int n;
    cin >> n;
    if (n <= 2) {
        cout << -1 << endl;
    } else {
        string t = "3 2 1";
        vector<int> a;
        for (int i = 4; i <= n; i++)a.push_back(i);
        cout << t;
        for (int i = 0; i < a.size(); i++)cout << " " << a[i];
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
//    cin >> T;
    T = 1;
    while (T--)slu();

}