51nod1010(枚举+二分)

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1010

题意：中文题诶～

思路：求第一个比 x (1<=x<=1e18)大或者等于的数y, 且y的因子只有2, 3, 5，即y=pow(2, i)*pow(3, j)*pow(5, k);

那么显然我们可以通过枚举i, j, k求出所有由2, 3, 5因子构成的数，并将其存入数组中，再二分查找数组中第一个大于等于x的数即为答案；

代码：

 #include <bits/stdc++.h>

 #define ll long long

 #define MAXN 100000

 using namespace std;

 ll a[MAXN];

 const ll inf=1e18;

 ll get_pow(ll x, int n){

     ll ans=;

     while(n){

         if(n&){

             ans*=x;

         }

         x*=x;

         n>>=;

     }

     return ans;

 }

 void geloutingyu(void){ //**注意不能直接用pow()，会有精度问题

     int pos=;

     for(ll i=; get_pow(, i)<=inf; i++){

         for(ll j=; get_pow(, i)*get_pow(, j)<=inf; j++){

             for(ll k=; get_pow(, i)*get_pow(, j)*get_pow(, k)<=inf; k++){

                 a[pos++]=get_pow(, i)*get_pow(, j)*get_pow(, k);

             }

         }

     }

 }

 int main(void){

     int t;

     ll x;

     geloutingyu();

     sort(a, a+MAXN);

     cin >> t;

     while(t--){

         cin >> x;

         if(x==){

             cout <<  << endl;

             continue;

         }

         int pos=lower_bound(a, a+MAXN, x)-a;

         cout << a[pos] << endl;

     }

     return ;

 }

巴特西

51nod1010(枚举+二分)

最新文章

热门文章