erfanul007

LOJ 1289

Apr 13th, 2021
433
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. // #include <iostream>
  3. // #include <cstdio>
  4. // #include <cstdlib>
  5. // #include <algorithm>
  6. // #include <cmath>
  7. // #include <vector>
  8. // #include <set>
  9. // #include <map>
  10. // #include <queue>
  11. // #include <stack>
  12. // #include <ctime>
  13. // #include <cassert>
  14. // #include <complex>
  15. // #include <string>
  16. // #include <cstring>
  17. // #include <bitset>
  18. using namespace std;
  19.  
  20. // #pragma GCC optimize("Ofast,no-stack-protector")
  21. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  22. // #pragma GCC optimize("unroll-loops")
  23.  
  24. #define ll              long long int
  25. #define ui              unsigned int
  26. #define vi              vector< int >
  27. #define vll             vector< ll >
  28.  
  29. #define sc              scanf
  30. #define pf              printf
  31. #define cspf(i)         pf("Case #%d: ", i)
  32. #define spc             pf(" ")
  33. #define line            pf("\n")
  34.  
  35. #define ff              first
  36. #define ss              second
  37. #define mp              make_pair
  38. #define pb              push_back
  39. #define ppb             pop_back
  40. #define tp(v,j)         get<j>(v)
  41. #define Log(b,x)        (log(x)/log(b))
  42.  
  43. #define FOR(i,x,y)      for(int i = int(x); i < int(y); i++)
  44. #define ROF(i,x,y)      for(int i = int(x)-1; i >= int(y); i--)
  45. #define clr(arr,x)      memset(arr, x, sizeof arr)
  46. #define vout(v,sz)      for(int w=0;w<sz;w++){if(w) spc; cout<<v[w];}
  47. #define all(v)          v.begin(), v.end()
  48. #define rall(v)         v.rbegin(), v.rend()
  49. #define unq(v)          sort(all(v)),(v).resize(unique(all(v))-v.begin())
  50. #define fastIO          ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
  51.  
  52. #define sc1(x)          sc("%d",&x);
  53. #define sc2(x,y)        sc("%d %d", &x, &y)
  54. #define sc3(x,y,z)      sc("%d %d %d", &x, &y, &z)
  55. #define scl1(x)         sc("%lld",&x);
  56. #define scl2(x,y)       sc("%lld %lld", &x, &y)
  57. #define scf1(x)         sc("%lf",&x);
  58. #define scf2(x,y)       sc("%lf %lf", &x, &y)
  59.  
  60. #define pf1(x)          pf("%d",x);
  61. #define pf2(x,y)        pf("%d %d", x, y)
  62. #define pfl1(x)         pf("%lld",x);
  63. #define pfl2(x,y)       pf("%lld %lld", x, y)
  64.  
  65. #define MOD             4294967296LL
  66. #define MaxN            100000000LL
  67. #define inf             0x3f3f3f3f
  68. #define PI              acos(-1.0)  // 3.1415926535897932
  69. #define eps             1e-9
  70.  
  71. #ifdef ERFANUL007
  72.     #define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
  73.     template < typename Arg1 >
  74.     void __f(const char* name, Arg1&& arg1){
  75.         cout << name << " = " << arg1 << std::endl;
  76.     }
  77.     template < typename Arg1, typename... Args>
  78.     void __f(const char* names, Arg1&& arg1, Args&&... args){
  79.         const char* comma = strchr(names, ',');
  80.         cout.write(names, comma - names) << " = " << arg1 <<" | ";
  81.         __f(comma+1, args...);
  82.     }
  83. #else
  84.     #define debug(...)
  85. #endif
  86.  
  87.  
  88. int N;
  89.  
  90. vector< ui > prime;
  91. vector< ui > ans;
  92. bitset< MaxN+1 > isPrime;
  93.  
  94. void precalc(){
  95.     isPrime.set();
  96.     ll i, j;
  97.     ui x;
  98.  
  99.     for(i=4; i <= MaxN; i += 2) isPrime[i] = 0;
  100.     prime.pb(2);
  101.     ans.pb(2);
  102.     for(i=3; i <= MaxN; i+=2){
  103.         if(isPrime[i]){
  104.             prime.pb(i);
  105.             x = ans.back() * i;
  106.             ans.pb(x);
  107.             for(j=i*i; j <= MaxN; j += (i*2)) isPrime[j] = 0;
  108.         }
  109.     }
  110.     N = prime.size()-1;
  111.     debug(N);
  112. }
  113.  
  114. int main()
  115. {
  116.     #ifdef ERFANUL007
  117.         clock_t tStart = clock();
  118.         freopen("input.txt", "r", stdin);
  119.         freopen("output.txt", "w", stdout);
  120.     #endif
  121.  
  122.     precalc();
  123.  
  124.     int t, ca=0, lo, hi, mid, inx, n, i, occ;
  125.     ui res;
  126.     scanf("%d", &t);
  127.  
  128.     while(t--){
  129.         scanf("%d", &n);
  130.         res = 1;
  131.         for(i=0; prime[i] * prime[i] <= n; i++){
  132.             occ = Log(prime[i], n) + eps;
  133.             // debug(prime[i], occ);
  134.             while(--occ){
  135.                 res *= prime[i];
  136.             }
  137.         }
  138.         // debug(res);
  139.         lo = 0, hi = N;
  140.         while(lo <= hi){
  141.             mid = (lo + hi)/2;
  142.             if(prime[mid] > n) hi = mid-1;
  143.             else{
  144.                 lo = mid+1;
  145.                 inx = mid;
  146.             }
  147.         }
  148.         res *= ans[inx];
  149.         printf("Case %d: %u\n", ++ca, res);
  150.     }
  151.  
  152.  
  153.     #ifdef ERFANUL007
  154.         fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
  155.     #endif
  156.  
  157.     return 0;
  158. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×