SHARE
TWEET

lotus.eater086

a guest Sep 16th, 2019 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<string>
  6. #include<vector>
  7. #include <ctime>
  8. #include<queue>
  9. #include<set>
  10. #include<map>
  11. #include<list>
  12. #include<stack>
  13. #include<iomanip>
  14. #include<cmath>
  15. #include<bitset>
  16.  
  17. #define LL long long
  18. #define endl "\n"
  19.  
  20. using namespace std ;
  21.    
  22. //
  23. template < typename T >
  24.  
  25. inline T read( T &x )
  26. {
  27.  
  28.     x = 0 ;
  29.  
  30.     int f = 0 ;
  31.  
  32.     char ch = getchar() ;
  33.  
  34.     while( ch < '0' || ch > '9' )  {
  35.  
  36.         f |= ( ch == '-' ) , ch = getchar() ;
  37.  
  38.     }
  39.  
  40.     while( ch >= '0' && ch <= '9' )  {
  41.  
  42.         x = ( x << 1 ) + ( x << 3 ) + ch - '0' , ch = getchar() ;
  43.  
  44.     }
  45.  
  46.     return x = f ? -x:x ;
  47.  
  48. }
  49. //
  50.  
  51. vector<LL> v ;
  52.  
  53. const LL MOD = 1e10 ;  
  54.  
  55. LL power( LL x , LL y)
  56. {
  57.     LL res = 1LL ;  
  58.  
  59.     while ( y > 0) {
  60.        
  61.         if (y & 1)
  62.             res = res * x ;  
  63.  
  64.        
  65.         y = y >> 1 ;
  66.  
  67.         x = x * x ;
  68.  
  69.     }
  70.  
  71.     return res ;  
  72.  
  73. }
  74.  
  75. void precalculate( void )
  76. {
  77.  
  78.     for( LL i = 0 ; i <= 31 ; i++ )  {  // 2
  79.  
  80.         for( LL j = 0 ; j <= 19 ; j++ )  {  // 3
  81.  
  82.             for( LL a = 0 ; a <= 12 ; a++ )  {  // 5  
  83.  
  84.                 for( LL b = 0 ; b <= 11 ; b++ )  {  // 7
  85.  
  86.                     LL x1 , x2 , x3 ;  
  87.  
  88.                     LL xyz = 1e9 ;
  89.  
  90.                     x1 = ( ( power(2,i)  )*( power(3,j) ) )  ;
  91.  
  92.                     if( x1 > xyz )  continue ;  
  93.  
  94.                     x2 = (  (  power(5,a)  )*(   power(7,b)   ) ) ;
  95.  
  96.                     if( x2 > MOD )  continue ;  
  97.  
  98.                     x3 = (  (x1 )*(  x2   )   )  ;  
  99.  
  100.                     if( x3  > xyz )  continue ;  
  101.  
  102.                     else v.emplace_back( x3 ) ;    
  103.  
  104.                 }
  105.  
  106.             }
  107.  
  108.         }
  109.  
  110.     }
  111.  
  112.     sort( v.begin() , v.end() ) ;  
  113.  
  114. }
  115.  
  116. LL bs( LL key )  // binary search
  117. {
  118.  
  119.     LL low = 0 , high = v.size() - 1 , ans = -1 ;
  120.  
  121.     while( low <= high )  {
  122.  
  123.         LL mid = low + ( high - low )/2 ;
  124.  
  125.         if( v[mid] == key )  {
  126.  
  127.             return key ;
  128.  
  129.         }
  130.  
  131.         else if( v[mid] > key )  {
  132.  
  133.             ans = v[mid] ;
  134.  
  135.             high = mid-1 ;
  136.  
  137.         }
  138.  
  139.         else  {
  140.  
  141.             low = mid+1 ;  
  142.  
  143.         }
  144.  
  145.     }
  146.  
  147.     return ans ;
  148.  
  149. }
  150.  
  151. void solve( void )
  152. {
  153.  
  154.     precalculate() ;     // making numbers in global vector using 2,3,5,7
  155.  
  156.     int t ;
  157.  
  158.     read( t ) ;
  159.  
  160.     while( t-- )  {
  161.  
  162.         LL n ;
  163.  
  164.         read( n ) ;
  165.  
  166.         LL output = bs( n ) ;
  167.  
  168.         printf( "%lld\n", output ) ;  
  169.  
  170.     }
  171.  
  172. }
  173.  
  174. int main( void )
  175.  
  176. {
  177.  
  178.     //ios_base::sync_with_stdio( false ) ;  cin.tie( NULL ) ;  cout.tie( NULL ) ;
  179.  
  180.     #ifndef ONLINE_JUDGE
  181.         freopen( "input.txt" , "r" , stdin ) ;
  182.         freopen( "output.txt" , "w" , stdout ) ;  
  183.     #endif
  184.  
  185.     if( 0 )  {
  186.  
  187.         int t = 100 ;
  188.  
  189.         for( int i = 1 ; i <= t ; i++ )  solve() ;
  190.  
  191.     }
  192.  
  193.     else  {
  194.  
  195.         solve() ;
  196.  
  197.     }
  198.  
  199.     #ifndef ONLINE_JUDGE
  200.         cout << "\nTime Elapsed: " << 1.0*clock()/CLOCKS_PER_SEC << " sec\n" ;
  201.    #endif
  202.  
  203.     return 0 ;
  204.  
  205. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top