/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
正整数 N,K が与えられます。
以下の条件を全て満たす長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) のうち、 A_N の値が最小となるものを一つ求めてください。
- A は広義単調増加である。すなわち、 1\le i\le N-1 に対し A_i \le A_{i+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_N の値が最小となる A を以下の形式で出力せよ。
A_1 A_2 \ldots A_N
条件を全て満たし A_N の値が最小となる A が複数ある場合、どれを出力しても正答となる。
入力例 1
2 5 3 2 3
出力例 1
1 2 3 4 5 4 7
1 つ目のテストケースについて考えます。
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_N の値が 5 より小さく条件を全て満たすような A は存在しないので、A=(1,2,3,4,5) を出力すると正答となります。
この他にも、 A=(2,3,4,5,5) や A=(2,3,3,5,5) などを出力しても正答となります。
Score : 600 points
Problem Statement
You are given positive integers N and K.
Find one length-N sequence of positive integers A=(A_1,A_2,\ldots,A_N) with the minimum value of A_N among the ones that satisfy all of the following conditions.
- A is non-decreasing. That is, A_i \le A_{i+1} for 1\le i\le N-1.
- \displaystyle \sum_{i=1}^{N-1} (A_{i+1} \bmod A_i)=K.
You are given T test cases; solve each of them.
Constraints
- 1\le T \le 10^5
- 2\le N \le 2\times 10^5
- The sum of N over all test cases is at most 2\times 10^5.
- 1\le K\le 10^9
- 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 K
Output
Output the answers for each test case in order, separated by newlines.
For each test case, print A that satisfies all conditions and has the minimum value of A_N in the following format:
A_1 A_2 \ldots A_N
If there are multiple A that satisfy all conditions and have the minimum value of A_N, any of them will be accepted.
Sample Input 1
2 5 3 2 3
Sample Output 1
1 2 3 4 5 4 7
Consider the first test case.
A=(1,2,3,4,5) is non-decreasing and satisfies \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, so it satisfies all conditions.
There does not exist an A that satisfies all conditions and has a value of A_N less than 5, so printing A=(1,2,3,4,5) will be accepted.
Other than this, printing A=(2,3,4,5,5) or A=(2,3,3,5,5) will also be accepted.