分数: 600 点
问题陈述
给你正整数 N 和 K.
找到一个长度-N 正整数序列 A=(A_1,A_2,\ldots,A_N) 的最小值为 A_N 满足以下所有条件。
- A 不减少。也就是说, A_i \le A_{i+1} 为 1\le i\le N-1.
- \displaystyle \sum_{i=1}^{N-1} (A_{i+1} \bmod A_i)=K.
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1\le T \le 10^5
- 2\le N \le 2\times 10^5
- 总和 N 所有测试用例最多 2\times 10^5.
- 1\le K\le 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N K
输出
按顺序输出每个测试用例的答案,以换行符分隔。
对于每个测试用例,打印 A 满足所有条件并具有最小值 A_N 采用以下格式:
A_1 A_2 \ldots A_N
如果有多个 A 满足所有条件并具有最小值 A_N,其中任何一个都会被接受。
示例输入 1
2 5 3 2 3
示例输出 1
1 2 3 4 5 4 7
考虑第一个测试用例。
A=(1,2,3,4,5) 是非递减且满足 \displaystyle \sum_{i=1}^{N-1} (A_{i+1} \bmod A_i) = (2\bmod 1) + (3\bmod 2) + (4\bmod 3) + (5\bmod 4)=3=K,因此它满足所有条件。
不存在 A 满足所有条件且值为 A_N 小于 5,所以打印 A=(1,2,3,4,5) 将被接受。
除此之外,打印 A=(2,3,4,5,5) or A=(2,3,3,5,5) 也将被接受。