题目链接

https://www.luogu.com.cn/problem/U136049

我只是大自然的搬运工，这题目是蓝桥杯的一道真题。我出了几个测试数据，就把它放到了洛谷的个人题库。

题目描述

  到x星球旅行的游客都被发给一个整数，作为游客编号。x星的国王有个怪癖，他只喜欢数字3,5和7。 国王规定，游客的编号如果只含有因子：3,5,7,就可以获得一份奖品。

  我们来看前10个幸运数字是： 3 5 7 9 15 21 25 27 35 45。 因而第11个幸运数字是：49

  小明领到了一个幸运数字 x，他去领奖的时候，人家要求他准确地说出这是第几个幸运数字，否则领不到奖品。

输入格式

小明领取到的幸运数字 x。 1 <= x < 10^14。

输出格式

一个正整数，表示这是第几个幸运数字

输入输出样例

输入 #1复制

49

输出 #1复制

11

说明/提示

1 <= x < 10^14

解法1

维护一个计数变量，暴力枚举从3到x，每个数都判断是否是幸运数，如果是幸运数，计数变量+1。

难点在于如何判断一个数是否是幸运数。由于一个幸运数的因子只有3，5，7。因此只需要让它不断除以3直到不能整除3为止，然后不断除以5直到不能整除5为止，然后不断除以7直到不能整除7为止。最后的结果如果是1，则原数就是幸运数。

但是对于x最大可达10^14，显然对于这样的数据规模，这种算法会超时。

#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; typedef long long ll; int main() { ll x; scanf("%lld", &x); int ans=0; for(ll i=3; i<=x; i++) { ll t=i; while(t%3==0) t /= 3; while(t%5==0) t /= 5; while(t%7==0) t /= 7; if(t==1) { ans++; if(i==x) break; } } printf("%d", ans); return 0; }

解法2

来自于某猛女 Orz。。。，那么可以通过三重循环枚举阶数，统计  的种数。 但是需要注意两个问题

1、pow(3,a)*pow(5,b)*pow(7,c) 可能会超出long long返回，所以不要用 long long 去接收。要用 double类型接收，而 pow() 的返回值本身就是 double

2、为什么 if 里面的条件是 < 而不是 <= ？因为这么枚举多算了 x=1（事实上这是不合法的），所以不取等号（不算上等于x的情况）刚好就抵掉了

#include<stdio.h> #include<math.h> int main(void) { long int n,m; scanf("%ld",&n); int a,b,c,count=0; for(a=0 ; pow(3,a)<n ; a++ ) { for(b=0 ; pow(5,b)<n ; b++) { for(c=0 ; pow(7,c)<n ; c++) { if(pow(3,a)*pow(5,b)*pow(7,c)<n) { count++; } } } } printf("%d",count); return 0; }

 解法3

假设已经知道前 i–1 个幸运数，如何推出第 i 个幸运数? 显然第 i 个数可以由前 i-1 个数推出来。第 i 个数有可能是前 i-1 个数中的某个数乘以3得到，也可能是前 i-1 个数中的某个数乘以5得到，也可能是前 i-1 个数中的某个数乘以7得到。不太好表述，直接看代码，也比较好懂。

#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; typedef long long ll; vector<ll> num; // 求 num[ num.size() ] 的待定值 // 返回一个大于 num[ num.size()-1 ] 的待定值 // 可用二分法优化，但没必要 ll getNum(int key) { for(int i=0; i<num.size(); i++) { ll t = num[i]*key; if(t > num[ num.size()-1 ]) return t; } } int main() { num.push_back(3); num.push_back(5); num.push_back(7); ll x; scanf("%lld", &x); while(num[ num.size()-1 ] < x) { ll a = getNum(3); ll b = getNum(5); ll c = getNum(7); ll t = min(a, min(b, c)); num.push_back(t); } printf("%d", num.size()); return 0; }

解法4

显然，对于解法3的 getNum() 可以换成 二分法 来优化！ 对比一下耗时，变化不大，因为 对于测试数据中最大的 x,  不定长数组 num 的元素个数也只是差不多2000而已，所以对于这个优化，效果不是很明显。

#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; typedef long long ll; vector<ll> num; // 二分法 ll getNum(int key) { int l=0, r=num.size()-1; while(l<r) { int m=(l+r)/2; if (num[m]*key <= num[ num.size()-1 ]) l=m+1; else r=m; } return num[r]*key; } int main() { num.push_back(3); num.push_back(5); num.push_back(7); ll x; scanf("%lld", &x); while(num[ num.size()-1 ] < x) { ll a = getNum(3); ll b = getNum(5); ll c = getNum(7); ll t = min(a, min(b, c)); num.push_back(t); } printf("%d", num.size()); return 0; }