Build Permutation

题意翻译

我们认为一个序列 $a$ 是优秀的，当且仅当其任意一个元素加上其下标是完全平方数。 形式化地， $\forall i\in[0,n), \sqrt{a_i+i}\in\mathbb{N}$ 。 给定 $n$，求 $0$ 至 $n-1$ 的一个优秀排列，或者判断不存在这样的排列。 值得注意的是，本题中特殊规定下标从 $0$ 开始，到 $n-1$ 结束。 多测，$\sum n\leq10^5$ 。

题目描述

A $ \mathbf{0} $ -indexed array $ a $ of size $ n $ is called good if for all valid indices $ i $ ( $ 0 \le i \le n-1 $ ), $ a_i + i $ is a perfect square $ ^\dagger $ . Given an integer $ n $ . Find a permutation $ ^\ddagger $ $ p $ of $ [0,1,2,\ldots,n-1] $ that is good or determine that no such permutation exists. $ ^\dagger $ An integer $ x $ is said to be a perfect square if there exists an integer $ y $ such that $ x = y^2 $ . $ ^\ddagger $ An array $ b $ is a permutation of an array $ a $ if $ b $ consists of the elements of $ a $ in arbitrary order. For example, $ [4,2,3,4] $ is a permutation of $ [3,2,4,4] $ while $ [1,2,2] $ is not a permutation of $ [1,2,3] $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The only line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the permutation $ p $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, output $ n $ distinct integers $ p_0, p_1, \dots, p_{n-1} $ ( $ 0 \le p_i \le n-1 $ ) — the permutation $ p $ — if the answer exists, and $ -1 $ otherwise.

输入输出样例

输入样例 #1

3
3
4
7

输出样例 #1

1 0 2 
0 3 2 1 
1 0 2 6 5 4 3

说明

In the first test case, we have $ n=3 $ . The array $ p = [1, 0, 2] $ is good since $ 1 + 0 = 1^2 $ , $ 0 + 1 = 1^2 $ , and $ 2 + 2 = 2^2 $ In the second test case, we have $ n=4 $ . The array $ p = [0, 3, 2, 1] $ is good since $ 0 + 0 = 0^2 $ , $ 3 + 1 = 2^2 $ , $ 2+2 = 2^2 $ , and $ 1+3 = 2^2 $ .

题目大意：
一个从0开始索引的数组a，如果对于所有有效的索引i（0≤i≤n-1），a[i]+i是一个完全平方数，则称该数组是优秀的。给定整数n，找到[0,1,2,…,n-1]的一个优秀排列p，或者判断不存在这样的排列。

输入输出数据格式：
输入格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例只有一行，包含一个整数n（1≤n≤10^5）——排列p的长度。
保证所有测试用例的n之和不超过10^5。

输出格式：
对于每个测试用例，如果存在答案，输出n个不同的整数p[0], p[1], …, p[n-1]（0≤p[i]≤n-1）——排列p；否则输出-1。题目大意： 一个从0开始索引的数组a，如果对于所有有效的索引i（0≤i≤n-1），a[i]+i是一个完全平方数，则称该数组是优秀的。给定整数n，找到[0,1,2,…,n-1]的一个优秀排列p，或者判断不存在这样的排列。 输入输出数据格式： 输入格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例只有一行，包含一个整数n（1≤n≤10^5）——排列p的长度。 保证所有测试用例的n之和不超过10^5。 输出格式： 对于每个测试用例，如果存在答案，输出n个不同的整数p[0], p[1], …, p[n-1]（0≤p[i]≤n-1）——排列p；否则输出-1。