题目思路

考虑构造，首先第一个数字必然是1，可以得到0-k的所有元素，此时无法得到k +1，那么就再加入k + 1，此时可以枚举到0到k * (k + 1) + k的所有数字。

如果此时得到的最大值也无法大于等于n，那就继续加入下一个数字，这个数字取为当前可以取到的最大值+1。

代码

Python

T = int(input())

for _ in range(T):
    n, k = map(int, input().split())
    ans = 1
    cur_mx = k
    while cur_mx < n:
        ans += 1
        cur_mx += (cur_mx + 1) * k

    print(ans)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int ans = 1;
            long cur_mx = k;
            while (cur_mx < n) {
                ++ans;
                cur_mx += (cur_mx + 1) * k;
            }
            System.out.println(ans);
        }
    }
}

c++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T = 0;
    cin >> T;
    while (T) {
        int n = 0, k = 0;
        cin >> n >> k;
        int ans = 1;
        long long max = k;
        while (max < n) {
            max += (max + 1) * k;
            ans ++;
        }
        cout << ans << endl;
        T --;
    }
    return 0;
}

会员可通过查看《已通过》的提交记录来查看其他语言哦~

题目内容

给定$t$组询问，每次询问给出两个正整数$n$和$k$。

在每组询问中，你要找到尽可能少的不同的正整数，满足以下条件：

• 每个正整数在构成同一个数字时，都能用$0$~$k$次。

• 对于区间[$1,n$]里面的每一个数字，都能通过数字之间的组合而“构造”出来、

  这里的“构造”特指求和。更正式地，你需要找到$m$个数字$a_1,a_2,....,a_m$,使得每个$x∈[1,n]$,都能找到至少一组$x=a_1×y_1+a_2×y_2+...+a_m×y_m$（$0≤y_i≤k$）。

  由于数字组合不唯一，请输出最少的数字个数$m$。

输入描述

​ 每个测试文件均包含多组测试数据。第一行输入一个整数$T$($1≤T≤10^5$)代表数据组数，每组测试数据描述如下：

​ 在一行上输入两个整数$n$($1≤n≤10^9$)和$k$($1≤K≤10^9$)，其含义已在题目中说明。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表最少的满足条件的数字个数。

样例1

输入

3
1 1
3 2
5 2

输出

1 
2
2

说明

对于第一组测试数据，我们最少需要$1$个数字，数字是$1$。此时有$1=1$。

对于第二组测试数据，我们最少需要$2$个数字，数字是$1$和$2$。

此时有$\begin{cases}1=1\\3=1+1\\3=2+1\end{cases}$

对于第三组测试数据，我们最少需要$2$个数字，数字是$1$和$2$。

此时有

$\begin{cases}1=1\\2=1+1\\3=2+1\\4=2+2\\5=2+2+1\end{cases}$