蓝桥杯-2018-第几个幸运数字-c++/java/python3

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

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

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

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

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

35791521252735453 5 7 9 15 21 25 27 35 453579152125273545

因而第 111111 个幸运数字是： 494949

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

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

运行限制

最大运行时间：1s最大运行内存: 128M

解法一：Python 3 （个人感觉Python暴力很爽）
 

import os
import sys

# 请在此输入您的代码
count=0
for a in range(30):
    for b in range(30):
        for c in range(30):
            if 3**a*5**b*7**c<=59084709587505:
                count+=1
print(count-1)#要减掉abc都是0的情况

解法二：c++（暴力超时，在网络大世界中找到个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中元素的个数即为所求。

#include
using namespace std;
typedef long long L;
const L MAX = 59084709587505; //本题中的数
int main()
{
    int a[3]={3,5,7};
    L t = 1;
    set s; //set集合排序加去重
    while(1)
    {
        for(int i=0;i<3;i++) //生成数
        {
            L tt = t * a[i];
            if(tt<=MAX) s.insert(tt);
        }
        t = *(s.upper_bound(t));  //找出s中略大于t的数赋值给t
        if(t>=MAX) break; //结束循环
    }
    cout< 
解法三：Java 
 思路：只要根据条件，算出第几个只含有因子：3,5,7的数是59084709587505，用到了逆向思维
  
 
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
       long MAX =  59084709587505l;
        int count = 0;
        for ( long i = 0; Math.pow(3,i) < MAX; ++i)
            for ( long j = 0; Math.pow(5,j) < MAX; ++j)
                for ( long k = 0; Math.pow(7,k) < MAX; ++k)
                    if (Math.pow(3,i) * Math.pow(5,j) * Math.pow (7,k) < MAX )
                        count ++;
        System.out.println(count);              
    }
}