/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 700 点
問題文
正整数 M,K が与えられます。
以下の条件を全て満たす正整数 N と整数列 A=(A_1,A_2,\ldots, A_N) が存在するか判定し、存在するなら一つ求めてください。
- 1\le N\le M
- 0\le A_i < M (1\le i\le N)
- k\equiv A_i+A_j \pmod M を満たす添字の組 (i,j) が存在するような整数 0\le k < M がちょうど K 個存在する。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T\le 2\times 10^5
- 1\le K\le M\le 2\times 10^5
- 全てのテストケースにおける M の総和は 2\times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
M K
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、条件を全て満たす N,A が存在しない場合は No を出力せよ。
そうでない場合、条件を全て満たす N と A を以下の形式で出力せよ。
Yes N A_1 A_2 \ldots A_N
条件を全て満たす N と A が複数ある場合、どれを出力しても正答となる。
入力例 1
3 6 5 3 2 8 3
出力例 1
Yes 3 3 1 4 No Yes 2 0 1
1 つ目のテストケースについて、 A=(3,1,4) とすると
- k=0 ： (i,j)=(1,1) とすると 0\equiv 3+3\pmod 6 が成立する。
- k=1 ： (i,j)=(1,3) とすると 1\equiv 3+4\pmod 6 が成立する。
- k=2 ： (i,j)=(3,3) とすると 2\equiv 4+4\pmod 6 が成立する。
- k=3 ： 条件を満たす添字の組 (i,j) は存在しない。
- k=4 ： (i,j)=(1,2) とすると 4\equiv 3+1\pmod 6 が成立する。
- k=5 ： (i,j)=(2,3) とすると 5\equiv 1+4\pmod 6 が成立する。
となり、条件を満たす 0\le k < 6 はちょうど 5 個であることが分かります。
Score : 700 points
Problem Statement
You are given positive integers M,K.
Determine whether there exist a positive integer N and an integer sequence A=(A_1,A_2,\ldots, A_N) that satisfy all the following conditions, and if they exist, find one.
- 1\le N\le M
- 0\le A_i < M (1\le i\le N)
- There are exactly K integers 0\le k < M such that there exists a pair of indices (i,j) satisfying k\equiv A_i+A_j \pmod M.
You are given T test cases, so find the answer for each.
Constraints
- 1\le T\le 2\times 10^5
- 1\le K\le M\le 2\times 10^5
- The sum of M over all test cases is at most 2\times 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:
M K
Output
Output your solutions for the test cases in order, separated by newlines.
For each test case, if there are no N,A that satisfy all conditions, output No.
Otherwise, output N and A that satisfy all conditions in the following format:
Yes N A_1 A_2 \ldots A_N
If there are multiple N and A that satisfy the conditions, you may output any of them.
Sample Input 1
3 6 5 3 2 8 3
Sample Output 1
Yes 3 3 1 4 No Yes 2 0 1
For the first test case, if we set A=(3,1,4), then
- k=0: Setting (i,j)=(1,1), we have 0\equiv 3+3\pmod 6.
- k=1: Setting (i,j)=(1,3), we have 1\equiv 3+4\pmod 6.
- k=2: Setting (i,j)=(3,3), we have 2\equiv 4+4\pmod 6.
- k=3: There is no pair of indices (i,j) that satisfies the condition.
- k=4: Setting (i,j)=(1,2), we have 4\equiv 3+1\pmod 6.
- k=5: Setting (i,j)=(2,3), we have 5\equiv 1+4\pmod 6.
Thus, there are exactly 5 values of 0\le k < 6 that satisfy the condition.