算法

(数论、枚举) $O(\log^2 a)$

假设执行操作 $1$ 的次数为 $x$，执行操作 $2$ 的次数为 $y$ 。

首先注意到先做操作 $2$ 再做操作 $1$ 更优，因为 $\lfloor \frac{a}{b + 1}\rfloor \leqslant \lfloor \frac{a}{b}\rfloor$ 。

最坏情况，$a = 10^9$，$b = 2$ 时，最多需要 $\lfloor \log_2(10^9)\rfloor = 29$ 次操作可以使 $a = 0$。

我们只需要枚举执行操作 $2$ 的次数 $x$，并对于每个 $x$ 统计需要多少个操作 $1$，然后取所有情况的最小值即可。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::min;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int a, b;
        cin >> a >> b;
        int ans = 1e9;
        rep(i, 30) {
            if (b + i == 1) continue;
            int now = i;
            int x = a;
            while (x) {
                x /= b + i;
                now++;
            }
            ans = min(ans, now);
        }
        cout << ans << '\n';
    }

    return 0;
}