首页 > 代码库 > 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的数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。