51NOD 1010 只包含因子2 3 5的数(二分 + 预处理)

传送门

K的因子中只包括2 3 5。满足条件的前10个数是:2,3,4,5,6,8,9,10,12,15。
所有这样的K组成了1个序列S,现在给出1个数n,求S中 >= 给定数的最小的数。
例如:n = 13,S中 >= 13的最小的数是15,所以输出15。
Input
第1行:1个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000)
第2 – T + 1行:每行1个数N(1 <= N <= 10^18)
Output
共T行,每行1个数,输出>= n的最小的只包括因子2 3 5的数。
Input示例
5
1
8
13
35
77
Output示例
2
8
15
36
80
解题思路:
就是首先将所有的只含有2 3 5因子的数打1个表保存在1个数组里,然后2分查找第1个>=数组里的数,输出就好了。
上代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL INF = 1e18+100;///不能太小了
const int MAXN = 70*70*70;
LL a[MAXN];
int cnt = 0;
void Init()
{
cnt = 0;
for(LL i=1; i<INF; i*=2)///(注意i,j,k是LL的)
for(LL j=1; j*i<INF; j*=3)
for(LL k=1; i*j*k<INF; k*=5)
a[cnt++] = i*j*k;
}
int main()
{
Init();
sort(a, a+cnt);
int T;
cin>>T;
while(T--)
{
LL n;
scanf("%lld",&n);
printf("%lld\n",a[lower_bound(a+1,a+cnt+1,n)-a]);
}
return 0;
}
波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 51NOD 1010 只包含因子2 3 5的数(二分 + 预处理)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡