构造题

当 n 为偶数的时候，构造方案是显然的。只需选取 \frac{n}{2} 对正整数，并且让每一对相邻即可，这样每一对的距离都是 1，符合平方数的要求。关键是对于奇数情形的构造。这时候必然至少有某一个正整数出现了奇数次，从最小的符合要求的奇数 3 开始考虑，要使得它们两两之间的距离差均为平方数。

这三个数之间的距离刚好构成了勾股方程的一个解。众所周知，勾股方程的最小一组正整数解是 3^2+4^2=5^2，也就是下标最大为 26，此时最小的可构造序列长度为 27。利用这组勾股方程得到这样一个长度为 27 的构造：

const int sub[] = {1, 2, 2, 3, 3, 4, 4, 5, 5, 1, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 1, 6};

其中的数字 1 就是根据勾股方程的解来构造的。对于更大的奇数，截取前 27 项，剩下的部分刚好长度为偶数，可以按照偶数策略来构造。由于这是勾股方程的最小解，因此对于更小的奇数无法构造，均为无解。

其他的细节可以参考下面的代码。

Code

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define Ciallo main
#define int long long
using namespace std;
const int sub[] = {1, 2, 2, 3, 3, 4, 4, 5, 5, 1, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 1, 6};

int T, n, k;

inline void solve() {
    cin >> n;
    if(n % 2 == 0) {
        for(int i = 1; i <= n / 2; i++)
            cout << i << ' ' << i << ' ';
        cout << endl;
    } else{
        if(n < 27)
            cout << -1 << endl;
        else{
            for(int i : sub)
                cout << i << ' ';
            n -= 27;
            for(int i = 14; i <= 13 + n / 2; i++)
                cout << i << ' ' << i << ' ';
            cout << endl;
        }
    }
}

signed Ciallo() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> T;
    while(T--)
        solve();

    return 0;
}