算法-第几个幸运数

问题描述

到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

5

7

Set

cycle one

3

5

7

9

15

21

3分别乘以3、5、7并加入到Set集合中

cycle two

3

5

7

9

15

21

25

35

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的数赋值给t
        if(t>=MAX) break; //结束循环
    }
    cout<<s.size()<<endl;
}

正确答案

---

练习题：

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

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

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

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

3 5 7 9 15 21 25 27 35 45  

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

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

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

以下选项错误的是？

答案：

typedef long long LL;
const LL MAX = 59084709587505;
int main()
{
    int a[3] = {3, 5, 7};
    LL tou = 1;
    set<LL> s;
    while (true)
    {
 
        for (int i = 0; i < 3; i++)
        {
            LL tt = tou * a[i];
            if (tt <= MAX)
                s.insert(tt);
        }
        tou = s.upper_bound(tou);
        if (tou >= MAX)
            break;
    }
    cout << s.size() << endl;
    return 0;
}