牛客周赛 Round 58

D 好好好数

题目大意：

定义k-好数为：可以表示为若干个不同的k的整次幂之和的数字

例如30= 3^3 + 3^1 ,30是一个3-好数

给定一个数n，n最少可以表示成几个k-好数的和

赛事错误思路：

将n转化为k进制，然后将数位上的数字求和，当时想的是求n转换为n个k的整次幂的数

正解：

k进制数位上的最大值即为解，因为一个k-好数可以表示为多个k的整次幂的和，

比如三进制下 1010 ，可用（1000+10） 两个k的整次幂表示一个3-好数，

而2020 ，可用 （1000+10）+（1000+10）

2010 可用 （1000+10）+（1000）

注意：

k==1

n可表示为1^1 +1^2+…直到等于n ，因此k==1时 输出1

n<k

只能将n表示为n个k^0 ，因此n<k时 输出n

Solve

void solve()
{ int n,k;cin>>n>>k;if(n<k){cout<<n<<endl;return;}if(k==1){cout<<"1"<<endl;return ;}int ans=0;while(n){ans=max(ans,n%k);n/=k;}cout<<ans<<endl;	
}