首页 > 代码库 > 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(枚举,打表)