题目描述：
有一天，小明给了你两个数字n和k，现在，你需要对数字n进行一下操作：
对于每一步操作，你可以选择下面其中一个项目：
1.将n的值减少1.
2.如果n能被k整除，可以使n/k
比如：n=27,k=3,你可以进行下列操作：27→26→25→24→8→7→6→2→1→0
请你计算出数字n变为0时最少需要的操作数。
输入：
第一行输入一个整数t（1≤t≤100），表示数据个数
接下来n行，每行2个整数n和k(1≤n≤1e18,2≤k≤1e18)
输出：
将数字n变为0的最小次数
输入样例：
3-;2
输出样例：
8
19
样例说明：
对于第一组数据，有：59→58→57→19→18→6→2→1→0
对于第二组数据，可以连续除以18个10使n变为1。
题目分析
首先可以先想到一个暴力的做法，也就是照着题目做
#include<cstdio>
int t;
long long n;
long long k;
int main(){
scanf("%d",&t);
while(t--)
{
long long ans=0;
scanf("%lld %lld",&n,&k);
while(n!=0)
{
if(n%k==0)
{
n/=k;
ans++;
}
else
{
ans++;
n--;
}
}
printf("%lld\n",ans);
}
return 0;
}
不出所料，果然，超时了
然后，寻找优化时，发现，也就只能优化–1的部分，也就是用%,把n削成能够被/k的地步
#include<cstdio>
int t;
long long n;
long long k;
int main(){
scanf("%d",&t);
while(t--)
{
long long ans=0;
scanf("%lld %lld",&n,&k);
while(n!=0)
{
if(n%k==0)
{
n/=k;
ans++;
}
else
{
ans+=n%k;
n-=n%k;
}
}
printf("%lld\n",ans);
}
return 0;
}
