51NOD 1010 只包含因子2 3 5的数（二分 + 预处理）

发布时间：2020-12-13 21:08:14 所属栏目：PHP教程来源：网络整理

导读：传送门 K的因子中只包括2 3 5。满足条件的前10个数是：2,3,4,5,6,8,9,10,12,15。所有这样的K组成了1个序列S，现在给出1个数n，求S中 = 给定数的最小的数。例如：n = 13，S中 = 13的最小的数是15，所以输出15。 Input 第1行：1个数T，表示后面用作输入测试

传送门

K的因子中只包括2 3 5。满足条件的前10个数是：2,3,4,5,6,8,9,10,12,15。
所有这样的K组成了1个序列S，现在给出1个数n，求S中 >= 给定数的最小的数。
例如：n = 13，S中 >= 13的最小的数是15，所以输出15。
Input
第1行：1个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行1个数N(1 <= N <= 10^18)
Output
共T行，每行1个数，输出>= n的最小的只包括因子2 3 5的数。
Input示例
5
1
8
13
35
77
Output示例
2
8
15
36
80
解题思路：
就是首先将所有的只含有2 3 5因子的数打1个表保存在1个数组里，然后2分查找第1个>=数组里的数，输出就好了。
上代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL INF = 1e18+100;///不能太小了
const int MAXN = 70*70*70;
LL a[MAXN];
int cnt = 0;
void Init()
{
    cnt = 0;
    for(LL i=1; i<INF; i*=2)///(注意i,j,k是LL的)
        for(LL j=1; j*i<INF; j*=3)
            for(LL k=1; i*j*k<INF; k*=5)
                    a[cnt++] = i*j*k;
}
int main()
{
    Init();
    sort(a,a+cnt);
    int T;
    cin>>T;
    while(T--)
    {
        LL n;
        scanf("%lld",&n);
        printf("%lldn",a[lower_bound(a+1,a+cnt+1,n)-a]);
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!