/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
正整数 N が与えられます。
以下の条件を全て満たす正整数列 A=(A_1,A_2,\ldots,A_N) が存在するか判定し、存在する場合は一つ求めてください。
- 1\le A_i\le 10^6
- \displaystyle \sum_{i=1}^N \frac1{A_i^2}=1
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T\le 500
- 1\le N\le 10^5
- 全てのテストケースにおける N の総和は 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、条件を全て満たす A が存在しない場合は No を出力せよ。
条件を全て満たす A が存在する場合は A を以下の形式で出力せよ。
Yes A_1 A_2 \ldots A_N
条件を全て満たす A が複数存在する場合、どれを出力しても正答となる。
入力例 1
4 4 2 1 17
出力例 1
Yes 2 2 2 2 No Yes 1 Yes 2 2 3 3 4 4 5 5 6 7 10 14 20 20 21 30 30
1 番目のテストケースについて考えます。
A=(2,2,2,2) に対し、\displaystyle \sum_{i=1}^N\frac1{A_i^2}=\frac14+\frac14+\frac14+\frac14=1 となるため条件を満たすことが確認できます。
Score : 600 points
Problem Statement
You are given a positive integer N.
Determine whether there exists a sequence of positive integers A=(A_1,A_2,\ldots,A_N) satisfying all of the following conditions, and if so, find one such sequence.
- 1\le A_i\le 10^6
- \displaystyle \sum_{i=1}^N \frac1{A_i^2}=1
You are given T test cases; solve each of them.
Constraints
- 1\le T\le 500
- 1\le N\le 10^5
- The sum of N over all test cases is at most 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N
Output
Output the answers for the test cases in order, separated by newlines.
For each test case, if no A satisfying all conditions exists, output No.
If an A satisfying all conditions exists, output it in the following format:
Yes A_1 A_2 \ldots A_N
If multiple A satisfying all conditions exist, any of them will be accepted.
Sample Input 1
4 4 2 1 17
Sample Output 1
Yes 2 2 2 2 No Yes 1 Yes 2 2 3 3 4 4 5 5 6 7 10 14 20 20 21 30 30
Consider the first test case.
For A=(2,2,2,2), we have \displaystyle \sum_{i=1}^N\frac1{A_i^2}=\frac14+\frac14+\frac14+\frac14=1, so we can confirm that the conditions are satisfied.