← 返回题目列表

AtCoder · arc208_b

B. 模之和

中文机器翻译题面 查看原题

分数: 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) 也将被接受。