まず、最適解となる \(A\) の中に \(i=1,2,\ldots,N-1\) に対し \(\displaystyle \left\lfloor\frac{A_{i+1}}{A_i}\right\rfloor=1\) を満たすものが存在します。

証明：

最適解となる \(A\) を一つ用意し、そこから整数列 \(A'\) を以下のように定義します。

• \(A_N'=A_N\)
• \(A_i'=A_{i+1}'-(A_{i+1} \bmod A_i)\)

この \(A'\) は \(A_i' \geq A_i\) を満たします。

証明：

\(i=N\) のときは明らかです。

\(i < N\) のとき \(i+1\) での成立を仮定すると、

\[ \begin{aligned} &\phantom{=} A_i'=A_{i+1}'-(A_{i+1} \bmod A_i) \\ &\geq A_{i+1}-(A_{i+1} \bmod A_i) \\ &=A_i \left\lfloor\frac{A_{i+1}}{A_i} \right\rfloor\\ &\geq A_i \end{aligned} \]

となるため数学的帰納法から従います。

この \(A'\) に対し

\[ \begin{aligned} &\phantom{=} \sum_{i=1}^{N-1} (A_{i+1}' \bmod A_i') \\ &=\sum_{i=1}^{N-1} ((A_{i}'+(A_{i+1} \bmod A_i)) \bmod A_i') \\ &=\sum_{i=1}^{N-1} ((A_{i+1} \bmod A_i) \bmod A_i') \\ &= \sum_{i=1}^{N-1}(A_{i+1} \bmod A_i) \end{aligned} \]

が成り立ち、さらに

\[ \begin{aligned} &\phantom{=}\left\lfloor \frac{A_{i+1}'}{A_i'} \right\rfloor \\ &=\left\lfloor \frac{A_{i}'+(A_{i+1} \bmod A_i)}{A_i'} \right\rfloor \\ &=1\ \ \left(\because 0 \le A_{i+1}\bmod A_i < A_i \le A_i' \right) \end{aligned} \]

も成り立ちます。したがって、最適解となる \(A\) であって \(i=1,2,\ldots,N-1\) に対し \(\displaystyle \left\lfloor\frac{A_{i+1}}{A_i}\right\rfloor=1\) を満たすものが構築できました。

上の事実より「\(i=1,2,\ldots,N-1\) に対し \(\displaystyle \left\lfloor\frac{A_{i+1}}{A_i}\right\rfloor=1\) を満たす」という条件を追加しても良いです。以降はこの条件も追加で考えます。

解法 \(1\) ： \(A_N\) の値で二分探索

ある正整数 \(c\) を選び「\(A_N=c\) と条件を全て満たす \(A\) が存在するか？」という判定問題を考えます。

\(\displaystyle \left\lfloor\frac{A_{i+1}}{A_i}\right\rfloor=1\) という条件より \(A_{i+1}\) が決まっている場合 \(A_i\) としてあり得る範囲は \(\displaystyle \left\lfloor\frac{A_{i+1}}2\right\rfloor+1\le A_i\le A_{i+1}\) です。この範囲は単調性があるので、 \(\displaystyle A_{i}=\left\lfloor\frac{A_{i+1}}2\right\rfloor+1\) として \(\displaystyle \sum_{i=1}^{N-1}(A_{i+1} \bmod A_i)\) を計算し、この値が \(K\) 以上であれば \(A_N=c\) と条件を全て満たす \(A\) が存在し、 \(K\) 未満なら存在しません。

以上より判定問題を元に決め打ち二分探索を行うことでこの問題を解くことができます。

以上を適切に実装することでこの問題に正答することができます。計算量はテストケースあたり \(O(N \log K)\) です。

実装例(Python3)

for _ in range(int(input())):
    n, k = map(int, input().split())
    ng, ok = 0, 2 * 10**9 + 2025
    while ok - ng != 1:
        vs = (ok + ng) >> 1
        val = vs
        for i in range(n - 1):
            val = val // 2 + 1
        if vs - val >= k:
            ok = vs
        else:
            ng = vs
    a = [-1] * n
    val = ok
    a[n - 1] = ok
    for i in range(n - 1):
        val = val // 2 + 1
        a[n - 2 - i] = val
    print(*a)

解法 \(2\) ： \(A_1\) の値から昇順に求める

\(A_i\) を固定した時に \(\displaystyle \left\lfloor \frac{A_{i+1}}{A_i}\right\rfloor = 1\) を満たす最大の整数 \(A_{i+1}\) は \(2A_i - 1\) です。したがって、 \(A_1=c\) 、\(A_{i+1}=2A_i - 1\) とすると \(A_n=(c-1)2^{n-1}+1\) となるため \(\displaystyle \sum_{k=1}^{N-1}\left(A_{k+1}\bmod A_k \right)=A_N - A_1 = (c-1)2^{N-1}\) となります。\(A_2\) 以降の項を適当に調整することで \((c-1)2^{N-1}\) 未満の値も作ることができるので、初項が満たすべき条件は \((c-1)(2^{N-1}-1) \geq K\) 、つまり \(\displaystyle c\geq 1+\frac{K}{2^{N-1}-1}\) です。この条件を満たす最小の \(c\) は \(\displaystyle c = 1 + \left\lceil\frac{K}{2^{N-1}-1}\right\rceil\) であるため、 \(\displaystyle A_1=1 + \left\lceil\frac{K}{2^{N-1}-1}\right\rceil\) として \(\displaystyle \sum_{k=1}^{N-1}\left(A_{k+1}\bmod A_k \right)=K\) を満たすように順に構成すれば良いです。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N)\) です。

実装例(Python3)

for _ in range(int(input())):
    n, k = map(int, input().split())
    a = [2 if n >= 50 else 2 + (k - 1) // (2 ** (n - 1) - 1)]
    for i in range(n - 1):
        a.append(2 * a[-1] - 1)
        k -= a[-1] - a[-2]
        if k < 0:
            a[-1] += k
            k = 0
    print(*a)