c++ - 从数字到0最快的方法

所以，我有一个这样的家庭作业：
给定两个数字n和k可以达到long long极限，我们执行这样的操作：
如果n = n / k可被n整除，则分配k
如果n不能被1整除，则将n减少k
找到从n到0的最小操作数。
这是我的解决办法

#define ll long long

ll smallestSteps(ll n, ll k) {
    int steps = 0;
    if (n < k) return n;
    else if (n == k) return 2;
    else {
        while (n != 0) {
            if (n % k == 0) {
                n /= k;
                steps++;
            }
            else {
                n--;
                steps++;
            }
        }
        return (ll)steps;
    }
}

我想这个解决办法是什么？
但我认为O(n/k)和n可能会非常大，因此程序可能会超过1s的时间限制。有没有更好的方法来做到这一点？
编辑1：我使用k使其更短

最佳答案

考虑到这些观察结果，可以改进算法：
如果n<k那么k|(n-m)对于任何阳性m都不会成立，所以答案是n步数。
如果(k|n)不适用，则它适用的最大值为m, m<n所以它需要n - (n%k)步，直到（k m）再次保持。
实际上，您只需要继续使用n%k（或依赖编译器进行优化）对余数进行除法，并将步数增加余数+1。

steps=0
while(n>0)
     mod = n%k
     n = n/k
     steps+=mod + 1
return steps

关于c++ - 从数字到0最快的方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56463164/