_no0B

Untitled

Nov 28th, 2021
623
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define N ((int)6e4 + 5)
  4. #define MOD ((int)1e9 + 7)
  5. #define MAX ((int)1e9 + 7)
  6. #define MAXL ((ll)1e18 + 7)
  7. #define MAXP ((int)1e3 + 7)
  8. #define thr 1e-8
  9. #define pi acos(-1)  /// pi = acos ( -1 )
  10. #define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
  11. #define endl "\n"
  12.  
  13. using namespace std;
  14.  
  15. int isPrime[N/32 + 2];
  16.  
  17. bool IsPrime(int num) /// returns 1 for prime
  18. {
  19.     if(num == 2) return 1;
  20.     if((num & 1) == 0)  return 0;
  21.     int idx  = num >> 5 , bit = num & 31;
  22.     if( ( isPrime[idx] & (1<<bit) ) != 0 ) return 0;
  23.     else return 1;
  24. }
  25.  
  26. vector < int > Sieve(int n)
  27. {
  28.     for(int i = 3; i * i <= n ; i += 2){
  29.         if(IsPrime(i)){
  30.             for(int j = i * i ; j <= n ; j += i<<1){
  31.                 int idx = j >> 5 , bit = j & 31;
  32.                 isPrime[idx] = isPrime[idx] | (1<<bit);
  33.             }
  34.         }
  35.     }
  36.     vector < int > prime;
  37.     prime.push_back(2);
  38.     for(int i = 3 ; i <= n ; i += 2){
  39.         if(IsPrime(i)) prime.push_back(i);
  40.     }
  41.     return prime;
  42. }
  43.  
  44.  
  45.  
  46. int NearestPowerOfTwo(int n)
  47. {
  48.     while(1){
  49.         if( (n & (n-1)) == 0 ) return n; /// power of two
  50.         n++;
  51.     }
  52. }
  53.  
  54. int main()
  55. {
  56.     /// problem: https://codeforces.com/problemset/problem/1062/B
  57.     vector < int > prime = Sieve(1e6);
  58.  
  59.     int n;
  60.     cin>>n;
  61.  
  62.     vector < pair < int , int > > vec;
  63.     for(int p:prime){
  64.         if(n % p == 0){
  65.             int cnt = 0;
  66.             while(n % p == 0){
  67.                 n /= p;
  68.                 cnt++;
  69.             }
  70.             vec.push_back({p , cnt});
  71.         }
  72.     }
  73.     int ans = 1;
  74.     bool multiply = 0;
  75.     int minPowerOfTwo = 777 , maxPowerOfTwo = -1;
  76.     for(auto p:vec){
  77.         ans *= p.first;
  78.         int cnt = p.second;
  79.         int nearestPowerOfTwo = NearestPowerOfTwo(cnt);
  80.         minPowerOfTwo = min(minPowerOfTwo , nearestPowerOfTwo);
  81.         maxPowerOfTwo = max(maxPowerOfTwo , nearestPowerOfTwo);
  82.         if(nearestPowerOfTwo > cnt) multiply = 1;
  83.     }
  84.  
  85.     if(minPowerOfTwo != maxPowerOfTwo) multiply = 1;
  86.     int opp = multiply;
  87.     while(maxPowerOfTwo > 1){
  88.         opp++;
  89.         maxPowerOfTwo /= 2;
  90.     }
  91.  
  92.     cout<<ans<<" "<<opp<<endl;
  93.  
  94.     return 0;
  95.  
  96. }
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
RAW Paste Data