首页 > 代码库 > hdu5878 I Count Two Three（二分+ 打表）

hdu5878 I Count Two Three（二分+ 打表）

2024-08-13 19:48:41   219人阅读

题目链接：hdu5878 I Count Two Three

题意：给出一个整数n, 找出一个大于等于n的最小整数m, 使得m可以表示为2^a * 3^b * 5^c * 7^d??.

题解：打表预处理出所有满足要求的数，排个序然后二分查找解决。

技术分享
 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 typedef long long ll; 5 const int N = 1e9; 6 ll s[10000]; 7 ll pow(ll a, ll b){ 8     ll r = 1; 9     while(b){10         if(b & 1)11             r *= a;12         a *= a;13         b >>= 1;14     }15     return r;16 }17 int cnt;18 void init(){19     ll i, j, k ,l, t;20     cnt = 0;21     for(i = 0; i < 31; ++i){22         for(j = 0; j < 20 ; ++j){23             for(k = 0 ;k < 14 ; ++k){24                 for(l = 0; l < 12; ++l){25                     t = pow(2, i) * pow(3, j);26                     if(t > 1e9)27                         break;28                     t *= pow(5, k);29                     if(t > 1e9)30                         break;31                     t *=pow(7, l);32                     if(t > 1e9)33                         break;34                     s[cnt++] = t;35                 }36             }37         }38     }39     sort(s, s + cnt);40 }41 void bi_search(int n){42     int l = 0,r = cnt - 1;43     while(l < r){44         int mid = l + (r - l)/2;45         if(s[mid] >= n)46             r = mid;47         else48             l = mid + 1;49     }50     printf("%I64d\n", s[l]);51 }52 int main(){53     int t, n;54     scanf("%d", &t);55     init();56     while(t--){57         scanf("%d", &n);58         bi_search(n);59     }60     return 0;61 }
View Code

 

hdu5878 I Count Two Three（二分+ 打表）


联系
我们