首页 > 代码库 > hdu5878(枚举,打表)

hdu5878(枚举,打表)

题目链接:hdu5878

题意:到一行输入t,表示下面有t组数据,然后下面t行每行输入一个数n;

定义x==2^a*3^b*5^c*7^d(a, b, c, d为自然数,x不大于1e+9);

要求对于每一个n输出>=n的最小x;

 

思路:由于x比较大,可以先打个表;

依次枚举a,b,c,d将所有不大于1e+9的x存到数组a中,再用;lower_bound()找一下即可;

 

代码:

#include<bits/stdc++.h>
#define MAXN 10000
#define MAX 1000000000
#define eps 1e-6
#define ll long long
using namespace std;

ll a[MAXN];

void get_number(void)  //***打表,将所有不大于1e+9的x存数组a中
{
    ll flag;
    int pos=0;
    for(int i=0; pow(2, i)<=MAX; i++)
    {
        for(int j=0; pow(2, i)*pow(3, j)<=MAX; j++)
        {
            for(int k=0; pow(2, i)*pow(3, j)*pow(5, k)<=MAX; k++)
            {
                for(int l=0; pow(2, i)*pow(3, j)*pow(5, k)*pow(7, l)<=MAX; l++)
                {
                    a[pos++]=pow(2, i)*pow(3, j)*pow(5, k)*pow(7, l);
                }
            }
        }
    }
}

int main(void)
{
    std::ios::sync_with_stdio(false), cin.tie(0), cin.tie(0);
    ll t, n;
    get_number();
    sort(a, a+MAXN);
    cin >> t;
    while(t--)
    {
        cin >> n;
        int pos=lower_bound(a, a+MAXN, n)-a;   //****二分查找第一个大于等于n的数,返回指针;
        cout << a[pos] << endl;
    }
    return 0;
}

 

hdu5878(枚举,打表)