大输入（递归函数）分段错误

Question

    ll solve(ll a, ll b, ll i){
        //base case
        if (a == 0) return i;
        if (b > a) return i+1;

        //recursive case
        if (b == 1) {
            return solve(a,b+1,i+1);
        }
        ll n = solve(a, b+1, i+1);
        ll m = solve(a/b, b, i+1);
        return min(n,m);
    }

int main(){
int t;  
cin >> t;
while(t--){
ll a, b;
cin >> a >> b;
cout << solve(a, b, 0)<< endl;

基本上问题来自codeforces(1485A)。问题是，当我给一些大的输入，如50000000a和5b时，这会给我带来分段错误，而代码对较小的输入很好。请帮我解决。

Answer 1

使用递归是一个糟糕的选择。你需要做所有明显的算法优化。

关键的见解是，对于任何在增加b之前进行除法的路径，都有一个在增加b之前不进行除法的路径是一样好的或更好的。当你可以除以一个更大的数字时，为什么要除以一个更小的数字，如果你无论如何都要使用这些步骤来增加数字呢？

有了这种洞察力，并且去掉递归，解决这个问题就变得微不足道了：

#include <iostream>

unsigned long long divisions(unsigned long long a, unsigned long long b)
{
    // figure out how many divide operations we need
    int ops = 0;
    while (a > 0)
    {
        a/=b;
        ops++;
    }
    return ops;
}

unsigned long long ops(unsigned long long a, unsigned long long b)
{
    // figure out how many divides we need with the smallest possible b
    unsigned long long min_ops = (b == 1) ? (1 + divisions(a, b+1)) : divisions(a, b);

    // try every sensible larger b to see if it takes fewer operations
    for (unsigned long long num_inc = 1; num_inc <= min_ops; ++num_inc)
    {
        unsigned long long ops = num_inc + divisions (a, b + num_inc);
        if (ops < min_ops)
            min_ops = ops;
    }
    return min_ops;
}

int main(void)
{
    int t;
    std::cin >> t;
    while (t--)
    {
       unsigned long long a, b;
       std::cin >> a >> b;
       std::cout << ops(a, b) << std::endl;
    }
}