【题解】「CF1175A」From Hero to Zero

题目

题目描述

You are given an integer $n$ and an integer $k$ .

In one step you can do one of the following moves:

• decrease $n$ by $1$ ;
• divide $n$ by $k$ if $n$ is divisible by $k$ .

For example, if $n = 27$ and $k = 3$you can do the following steps: $27 \rightarrow 26 \rightarrow 25 \rightarrow 24 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$

You are asked to calculate the minimum number of steps to reach $0$ from $n$.

输入格式

The first line contains one integer $t$ ( $1 \le t \le 100$ ) — the number of queries.

The only line of each query contains two integers $n$ and $k$ ( $1 \le n \le 10^{18}$ , $2 \le k \le 10^{18}$).

输出格式

For each query print the minimum number of steps to reach $0$ from $n$ in single line.

翻译

给整数 $n,k$，每次你可以做如下两个操作之一

• 将 $n$ 减 $1$

• 将 $n$ 除以 $k$ （前提： $n$ 是 $k$ 的倍数）

试求让 $n$ 变为 $0$ 的最小操作次数。

输入输出样例

输入

2
59 3
1000000000000000000 10

输出

8
19

---

题解

一道水题，贪心+一点点简单的优化即可

基本贪心思路

过程

对于每一个 $n$:

• 如果 $n$为 $k$的倍数，则进行 $n/k$的操作，操作数 $+1$
• 否则 $n-1$,操作数 $+1$

这样做一定最优

证明

贪心贪就完了，给什么证明(bushi

如果在明明能用 $n/k$的时候使用了 $n-1$

这样减完后就不可能再用 $n/k$的操作，直到减了 $k$次，此时 $n$变为 $n-k$，而如果你依然不金盆洗手，还这样干，就需要连减很多次才可以到达 $n/k$，而人家一次就到了

如果你认识到了错误，不再一个一个减，开始使用除的办法

现在 $n-k$变为 $(n-k)/k$,即 $n/k+1$,跟前面的 $n/k$还差 $1$步，这还不算上之前白白浪费了这么多步

所以，该选择 $n/k$的时候还是选择TA吧

代码实现

有了思路，代码实现还不简单吗？

#include<cstdio>
#include<iostream>
using namespace std;
int main(){int t;scanf("%d",&t);while(t--){long long n,k;scanf("%lld %lld",&n,&k);long long tot=0;while(n!=0){if(n%k==0){n/=k;tot++;}else{n--;tot++;}}printf("%lld\n",tot);}
return 0;
} 

于是，这个简单的代码就这样简简单单的TLE掉了

什么情况？考虑优化

优化

那里一点一点吧 $n$减少成 $k$的倍数的地方是不是有点蛋疼？

我们就不能直接把 $n$一步变为 $k$的倍数吗

想到这里，你距离AC就只剩一步了！

每次如果 $n$不是 $k$的倍数，就直接把 $n$减成 $k$的倍数，并加上相应的步数

代码

#include<cstdio>
#include<iostream>
using namespace std;
int main(){int t;scanf("%d",&t);while(t--){long long n,k;scanf("%lld %lld",&n,&k);long long tot=0;while(n!=0){if(n%k==0){n/=k;tot++;}else{long long mm=n%k;n-=mm;tot+=mm;}}printf("%lld\n",tot);}
return 0;
}

The End