From Hero to Zero

题目描述：

有一天，小明给了你两个数字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;

}

巴特西

From Hero to Zero

题目描述：

题目分析

最新文章

热门文章