算法题每日一练 --- 第 9 天：第几个幸运数字

一、问题描述

到 X 星球旅行的游客都被发给一个整数，作为游客编号。

X 星的国王有个怪癖，他只喜欢数字 3，5 和 7。

国王规定，游客的编号如果只含有因子：3，5，7 就可以获得一份奖品。

我们来看前 10 个幸运数字是：

3 5 7 9 15 21 25 27 35 45

因而第 11 个幸运数字是： 49

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

请你帮小明计算一下，59084709587505 是第几个幸运数字。

二、题目要求

考察

1.for循环，数学思想2.建议用时5~15min

运行限制

• 最大运行时间：1s

• 最大运行内存: 128M

三、问题分析

首先，编号只能含有 3，5，7 这三个因子的话。一开始我想使用 for 循环，把从 1 到 59084709587505 中间的数字一个个判断。

后来发现不行，一个问题是规模太大没法彻底解决问题，另一个无法计算是否只含有 3，5，7 这三个数字。

后来，我又想到了另一个思路，就是既然你只含有 3，5，7，那我就判断这个数由几个 3，5，7 相乘得到，只要这个数小于目标数字，那么初始定义的 sum=0，计数器 sum++，最后输出结果。

拓展：

• 头文件 #include<math.h>里面的 pow(2,k)，可以计算 2 的 k 次方

• 目标数字太大，超出 int 存储范围，更改为 long longg int 存储

四、编码实现

#include <iostream>#include<math.h>//pow的头文件 using namespace std;int main(){  int i,j,k,sum=0;//初始化   long long int n=59084709587505;//目标数字太大，超出int存储范围，更改为long longg int 存储  for(i=0;pow(3,i)<=n;i++)//第一层3的次方   {    for(j=0;pow(5,j)<=n;j++)//第二层5的次方     {      for(k=0;pow(7,k)<=n;k++)//第三层7的次方       {        if(pow(3,i)*pow(5,j)*pow(7,k)<=n)//所有次方相乘小于目标数字         {          sum++;//sum++        }      }    }  }  cout<<sum-1;//因为0 0 0这种情况不算在内，去除     return 0;}

五、输出结果

输出结果为：1905