🎈 原创

第九届蓝桥杯 试题D：第几个幸运数

试题 D：第几个幸运数

本题总分: 10分

[问题描述]

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

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

国王规定，游客的编号如果只含有因子：3,5,7 就可以获得一份奖品。 前 10 个幸运数字是： 3 5 7 9 15 21 25 27 35 45 ，因而第 11 个幸运数字是：49

小明领到了一个幸运数字 59084709587505。

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

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

---

考试的时候想了半天都没做出来，一点思路都没有，看了题解才知道不要想太多，直接暴力就可以了。

这个数只含有因子3、5、7，也就是x = 3^i * 5^j * 7^k，那么就可以暴力枚举i、j、k，当这三部分相乘小于x时，这个数就是x的前面的一个，所以只要不断计数，求出x前面到底有多少个，就是x是第几个。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

long long x = 59084709587505;
long long cnt = 0;

int main(int argc, const char * argv[])
{
    for(long long i = 0; pow(3, i) <= x; i++)
        for(long long j = 0; pow(5, j) <= x; j++)
            for(long long k = 0; pow(7, k) <= x; k++)
                if(pow(3, i) * pow(5, j) * pow(7, k) <= x)
                    cnt++;

    cout << cnt - 1 << endl;

    return 0;
}

结果 1905

要注意的是因为 3^0 * 5^0 * 7^0 = 0也算在计数的过程中，但是题意中第一个数是从3开始的，所以最后结果要去掉0，也就是最后的cnt - 1