首页 > 代码库 > HDU 5878 I Count Two Three (打表+二分查找) -2016 ICPC 青岛赛区网络赛

HDU 5878 I Count Two Three (打表+二分查找) -2016 ICPC 青岛赛区网络赛

题目链接

题意:给定一个数n,求大于n的第一个只包含2357四个因子的数(但是不能不包含其中任意一种),求这个数。

题解:打表+二分即可。

 

#include <iostream>#include <math.h>#include <stdio.h>#include<algorithm>using namespace std;long long data[1000000],tot=0;int main(){    long long maxn = 1000000007;    long long a,b,c,d;    for(a=1;a<=maxn;a*=2)    for(b=1;a*b<=maxn;b*=3)    for(c=1;a*b*c<=maxn;c*=5)    for(d=1;a*b*c*d<=maxn;d*=7){        data[tot++] = a*b*c*d;    }    sort(data,data+tot);    int t,n;    scanf("%d",&t);    while(t--) {        scanf("%d",&n);        int pos = upper_bound(data,data+tot,n)-data;        if(pos>0&&data[pos-1]==n) pos--;        printf("%lld\n",data[pos]);    }    return 0;}

 

HDU 5878 I Count Two Three (打表+二分查找) -2016 ICPC 青岛赛区网络赛