本文主要是介绍2018蓝桥杯C++A组——第几个幸运数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
- 问题描述
- 题目解析
- 1.暴力法
- 2.Set生成法
- C++代码
- 暴力法代码
- Set生成法代码
- 正确答案
问题描述
到x星球旅行的游客都被发给一个整数,作为游客编号。
x星的国王有个怪癖,他只喜欢数字3,5和7。
国王规定,游客的编号如果只含有因子:3,5,7,就可以获得一份奖品。我们来看前10个幸运数字是:
3 5 7 9 15 21 25 27 35 45
因而第11个幸运数字是:49小明领到了一个幸运数字 59084709587505,他去领奖的时候,人家要求他准确地说出这是第几个幸运数字,否则领不到奖品。
请你帮小明计算一下,59084709587505是第几个幸运数字。
题目解析
1.暴力法
枚举3—目标数+check检查是否为3、5、7数字相乘。这道题不能采用这种算法,会严重超时。
2.Set生成法
Set集合在C++中是已经排好序的并去重的,因此就很适合这道题。
初始状态Set={3,5,7},取第一个数3,分别×3、×5、×7得到9、15、21,接着把9、15、21加入到Set中,此时Set={3,5,7,9,15,21},取略大于3的数5分别×3、×5、×7得到15、25、35,再加入到Set中,此时Set={3,5,7,9,15,21,25,35},如此下去…直到Set中再添加任何数都比原数大的时候循环退出,输出Set中元素的个数即为所求。
3分别乘以3、5、7并加入到Set集合中
5分别乘以3、5、7并加入到Set集合中
C++代码
暴力法代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAX = 49; //本题中的数带进去计算需16小时
int main()
{LL ans = 0;for(int i=3;i<=MAX;i++){int x = i;while(x%3==0) x/=3; //x可以被3整除while(x%5==0) x/=5; //x可以被5整除while(x%7==0) x/=7; //x可以被7整除if(x==1) ans++;}cout<<ans<<endl;
}
Set生成法代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAX = 59084709587505; //本题中的数
int main()
{int a[3]={3,5,7};LL t = 1;set<LL> s; //set集合排序加去重while(1){for(int i=0;i<3;i++) //生成数{LL tt = t * a[i];if(tt<=MAX) s.insert(tt);}t = *(s.upper_bound(t)); //找出s中略大于t的数赋值给tif(t>=MAX) break; //结束循环}cout<<s.size()<<endl;
}
正确答案
这篇关于2018蓝桥杯C++A组——第几个幸运数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!