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

Question

所以，我有这样的作业:

给定两个可以达到long long限制的数n和k，我们做这样的操作:

• 如果 n 可以被 k 整除，则分配 n = n/k
• 如果 n 不能被 k 整除，则将 n 减少 1

找到从 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和k可能非常大，因此程序可能会超过1s的时间限制。有没有更好的方法来做到这一点？

编辑 1:我使用 ll 来缩短

Answer 1

根据这些观察结果可以改进算法:

1. 如果n<k然后k|(n-m)永远不会对任何正的 m 成立。所以答案是n步骤。
2. 如果(k|n)不持有那么最大的数字m, m<n它所做的是n - (n%k) .所以需要 n%k步直到 (k|m) 再次成立。

实际上，您只需要使用 std::div 继续对余数进行除法运算即可(或依赖编译器优化)并增加步数+1。

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