cf签到题

89 阅读 0 评论 59 点赞

我是靠谱客的博主标致紫菜，这篇文章主要介绍cf签到题，现在分享给大家，希望可以做个参考。

题目大意
就是给你一个n和一个k
你可以做两种操作：一是减一二是除以k
让输出最小操作步骤

解题思路
一开始觉得签到题就直接遍历取模减一的然后第二个样例就超时了。
偷看了大佬的代码
基本思路是：先判断是否可以除尽k 如果可以步骤加一 n=n/k;
如果不可以说明肯定要进行减一的步骤然后想啊 n%k的值不就是剩下的要减一的那些个数吗所以步骤数加上 n%k
然后n变成 n-n%k;因为这是进行的减一的步骤
详细见代码

代码如下

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
	ll n,k,ans;
	int t;
	cin>>t;
	while(t--)
	{
		ans=0;
		cin>>n>>k;
		while(n!=0)
		{
			if(n%k==0)
			{
				ans++;
				n/=k;
			}
			else
			{
				ans+=(n%k);
				n-=(n%k);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

类似题
http://codeforces.com/problemset/problem/1176/A

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,ans=0,t;
	cin>>t;
	while(t--)
	{
		ans=0;
		cin>>n;
		while(n%2==0)
		{
			ans++;
			n/=2;
		}
		while(n%3==0)
		{
			ans+=2;
			n/=3;
		}
		while(n%5==0)
		{
			ans+=3;
			n/=5;
		}
		if(n==1)
		  cout<<ans<<endl;
		else
		 cout<<"-1"<<endl;
	}
	return 0;
}