I Count Two Three---hdu5878（打表+二分）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5878

题意：找到第一个>=n的数x, 满足 x = 2^a3^b5^c7^d；n<=1e9;

打表找到10e9以内的所有符合条件的数，然后二分找到即可；

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;
#define met(a, b) memset(a, b, sizeof(a))
#define N 100005
#define INF 0x3f3f3f3f
typedef long long LL;
const LL MAX = 1e9+10;

int cnt = 0;
LL f[N], a2[35], a3[35], a5[35], a7[35];

void Init()
{
    int P, Q, I, J;
    a2[0] = a3[0] = a5[0] = a7[0] = 1;

    for(int i=1; a2[i-1]*2<=MAX; i++, I=i) a2[i] = a2[i-1]*2;
    for(int i=1; a3[i-1]*3<=MAX; i++, J=i) a3[i] = a3[i-1]*3;
    for(int i=1; a5[i-1]*5<=MAX; i++, P=i) a5[i] = a5[i-1]*5;
    for(int i=1; a7[i-1]*7<=MAX; i++, Q=i) a7[i] = a7[i-1]*7;

    for(int i=0; i<I; i++)
    {
        for(int j=0; j<J; j++)
        if(MAX/a2[i] >= a3[j])
        for(int p=0; p<P; p++)
        if(MAX/(a2[i]*a3[j]) >= a5[p])
        for(int q=0; q<Q; q++)
        {
            if(MAX/(a2[i]*a3[j]*a5[p]) >= a7[q])
            f[cnt++] = a2[i]*a3[j]*a5[p]*a7[q];
        }
    }
    sort(f, f+cnt);
}


int main()
{
    Init();

    int T; LL n;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%I64d", &n);
        int pos = upper_bound(f, f+cnt, n) - f;
        if(f[pos-1] == n) pos--;
        printf("%I64d
", f[pos]);
    }
    return 0;
}