首页 > 代码库 > HDU 5878 I Count Two Three

HDU 5878 I Count Two Three

打表,二分。

满足条件的数字个数不多,可以全部找出来,排个序,每次询问的时候二分一下。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c=getchar(); x=0;    while(!isdigit(c)) c=getchar();    while(isdigit(c)) {x=x*10+c-0; c=getchar();}}const int maxn=100010;LL M=2e9;LL p[maxn];int sz=0;int main(){    LL a=1;    for(int i=0;;i++)    {        if(i!=0) a=a*2; if(a>M) break;        LL b=1;        for(int j=0;;j++)        {            if(j!=0) b=b*3; if(b>M||a*b>M) break;            LL c=1;            for(int s=0;;s++)            {                if(s!=0) c=c*5; if(c>M||a*b*c>M) break;                LL d=1;                for(int k=0;;k++)                {                    if(k!=0) d=d*7; if(d>M||a*b*c*d>M) break;                    p[sz++]=a*b*c*d;                }            }        }    }    sort(p,p+sz);    int T; scanf("%d",&T);    while(T--)    {        LL n; scanf("%lld",&n);        int L=0,R=sz-1,pos;        while(L<=R)        {            int m=(L+R)/2;            if(p[m]<n) L=m+1;            else if(p[m]==n) { pos=m; break; }            else pos=m,R=m-1;        }        printf("%lld\n",p[pos]);    }    return 0;}

 

HDU 5878 I Count Two Three