首页 > 代码库 > 51nod 1010 只包含因子2 3 5的数

51nod 1010 只包含因子2 3 5的数

基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题

K的因子中只包含2 3 5。满足条件的前10个数是:2,3,4,5,6,8,9,10,12,15。
所有这样的K组成了一个序列S,现在给出一个数n,求S中 >= 给定数的最小的数。
例如:n = 13,S中 >= 13的最小的数是15,所以输出15。
 
Input
第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000)第2 - T + 1行:每行1个数N(1 <= N <= 10^18)
Output
共T行,每行1个数,输出>= n的最小的只包含因子2 3 5的数。
Input示例
518133577
Output示例
28153680
小葵花妈妈课堂开课啦 因子就是一个合数分解成的那些质数,比如说15的因子就是1,3,5,15
打表+二分
屠龙宝刀点击就送
#include <algorithm>#include <iostream>#include <cstdio>#define Maxn 1e18+9999typedef long long LL;using namespace std;LL ans[100000],cnt;void qr(LL &x){    x=0;LL f=1;    char ch=getchar();    while(ch>9||ch<0)    {        if(ch==-) f=-1;        ch=getchar();    }    while(ch>=0&&ch<=9)    {        x=x*10+(LL)ch-48;        ch=getchar();    }    x*=f;}LL T,n;void init(){    for(LL i=1;i<Maxn;i*=2)    {        for(LL j=1;i*j<Maxn;j*=3)        {            for(LL k=1;i*j*k<Maxn;k*=5)            ans[cnt++]=i*j*k;        }    }}int main(){    init();    sort(ans,ans+cnt);    qr(T);    while(T--)    {        qr(n);        LL An=Maxn,l=1,r=cnt;        while(l<r)        {            int mid=(l+r)>>1;            if(ans[mid]>=n)                r=mid;            else l=mid+1;        }        cout<<ans[l]<<endl;    }    return 0;}

 

51nod 1010 只包含因子2 3 5的数