erfanul007

LOJ 1278

Sep 22nd, 2021
714
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long int
  5.  
  6. template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
  7. template <class T> inline T lcm(T a,T b) {a=abs(a);b=abs(b); return (a/gcd(a,b))*b;}
  8.  
  9. #ifdef ERFANUL007
  10.     #define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
  11.     template < typename Arg1 >
  12.     void __f(const char* name, Arg1&& arg1){
  13.         cout << name << " = " << arg1 << std::endl;
  14.     }
  15.     template < typename Arg1, typename... Args>
  16.     void __f(const char* names, Arg1&& arg1, Args&&... args){
  17.         const char* comma = strchr(names, ',');
  18.         cout.write(names, comma - names) << " = " << arg1 <<" | ";
  19.         __f(comma+1, args...);
  20.     }
  21. #else
  22.     #define debug(...)
  23. #endif
  24.  
  25. const ll N = 1e7;
  26. bool isPrime[N + 2];
  27. vector< ll > prime;
  28.  
  29. void sieve(){
  30.     memset(isPrime, 1, sizeof(isPrime));
  31.  
  32.     for(int i = 4; i <= N; i += 2) isPrime[i] = 0;
  33.  
  34.     for(ll i = 3; i*i <= N; i += 2){
  35.         if(!isPrime[i]) continue;
  36.         for(ll j = i*i; j <= N; j += (i * 2)) isPrime[j] = 0;
  37.     }
  38.     prime.push_back(2LL);
  39.  
  40.     for(int i=3; i <= N; i+=2){
  41.         if(isPrime[i]) prime.push_back(i);
  42.     }
  43. }
  44.  
  45. ll getcount(ll n){
  46.     ll divs = 1;
  47.     for(int i=1; i<prime.size() && prime[i] * prime[i] <= n; i++){
  48.         if(n % prime[i] == 0){
  49.             ll cnt = 0;
  50.             while(n % prime[i] == 0){
  51.                 cnt++;
  52.                 n /= prime[i];
  53.             }
  54.             divs *= (cnt + 1);
  55.         }
  56.     }
  57.     if(n > 1) divs *= 2;
  58.     return divs-1;
  59. }
  60.  
  61. int main(){
  62.     #ifdef ERFANUL007
  63.         clock_t tStart = clock();
  64.         freopen("input.txt", "r", stdin);
  65.         freopen("output.txt", "w", stdout);
  66.     #endif
  67.  
  68.     sieve();
  69.  
  70.     int t, cs = 0; scanf("%d", &t);
  71.  
  72.     while(t--){
  73.         ll n; scanf("%lld", &n);
  74.  
  75.         while(n % 2 == 0){
  76.             n/=2;
  77.         }
  78.         printf("Case %d: %lld\n", ++cs, getcount(n));
  79.     }
  80.  
  81.     #ifdef ERFANUL007
  82.         fprintf(stderr, ">>> Runtime : %.9f\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
  83.     #endif
  84.  
  85.     return 0;
  86. }
  87.  
  88. // a1 = n/m - (m-1)/2
RAW Paste Data