小H的糖果

NC222054. 小H的糖果

描述

小 H 生日的那一天，有人送给了小 H 1 颗糖果。小 H 觉得自己的糖果太少了，于是他学会了两种魔法：

使糖果数 +1。
让每一颗糖果分裂成 k 颗糖果，即让糖果总数乘以 k

小 H 想知道，他最少需要使用多少次魔法才能使糖果数刚好等于小 H 的幸运数字 n。

输入描述

每个测试点包含多组测试数据。
第一行一个正整数 T，表示数据组数。
接下来共 T 行，每行两个正整数 k,n，含义见题目描述。

输出描述

共 T 行，每行一个非负整数，表示使糖果数量刚好等于 n 的最少魔法使用次数。

示例1

输入:

3
2 3
2 9
114514 1919810

输出:

2
4
87602

说明:

样例解释：

对于第一组数据，可以连续使用2次魔法1，即1->2->3(数字表示使用魔法后的糖果数)

对于第二组数据，可以连续使用3次魔法2后再只用一次魔法1，即1->2->4->8->9。

数据范围：

对于 20% 的数据， $k,n \leq 10$ ；
对于 30% 的数据， $k,n \leq 100$ ；
对于另外 20% 的数据，所有的 k 都相同且 $n \leq 10^8$ ；
对于另外 20% 的数据， $k\leq 2$ ；
对于 100% 的数据， $1 \leq T \leq 10^6,1 \leq k,n \leq 10^{18}$ 。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 731ms, 内存消耗: 12668K, 提交时间: 2021-07-03 20:08:44

#include <bits/stdc++.h>
using namespace std;
#define int long long
int t,n,k;
signed main()
{
	cin>>t;
	while(t--){
		int ans=0;
		scanf("%lld %lld",&k,&n);
		if(k==1) ans=n+1;
		else {
			while(n){
				ans+=n%k+1;
				n/=k;
			}
		}
		printf("%lld\n",ans-2);
	}
}

上一题

下一题

详情