erfanul007

LOJ 1236

Sep 22nd, 2021
694
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. int pairsFormLCM(int n) {
  26.     int res = 0;
  27.     for(int i = 1; i <= n; i++ )
  28.         for(int j = i; j <= n; j++ )
  29.             if(lcm(i, j) == n){
  30.                 printf("%d * %d = %d\n", i, j, n);
  31.                 res++;
  32.             }
  33.     return res;
  34. }
  35.  
  36. const ll N = 1e7;
  37. bool isPrime[N + 2];
  38. vector< ll > prime;
  39.  
  40. void sieve(){
  41.     memset(isPrime, 1, sizeof(isPrime));
  42.  
  43.     for(int i = 4; i <= N; i += 2) isPrime[i] = 0;
  44.  
  45.     for(ll i = 3; i*i <= N; i += 2){
  46.         if(!isPrime[i]) continue;
  47.         for(ll j = i*i; j <= N; j += (i * 2)) isPrime[j] = 0;
  48.     }
  49.     prime.push_back(2LL);
  50.  
  51.     for(int i=3; i <= N; i+=2){
  52.         if(isPrime[i]) prime.push_back(i);
  53.     }
  54. }
  55.  
  56. ll getcount(ll n){
  57.     ll ans = 1;
  58.     for(int i=0; i<prime.size() && prime[i] * prime[i] <= n; i++){
  59.         if(n % prime[i] == 0){
  60.             ll cnt = 0;
  61.             while(n % prime[i] == 0){
  62.                 cnt++;
  63.                 n /= prime[i];
  64.             }
  65.             ans *= (cnt * 2 + 1);
  66.         }
  67.     }
  68.     if(n > 1) ans *= 3;
  69.     return (ans + 1)/2;
  70. }
  71.  
  72. int main(){
  73.     #ifdef ERFANUL007
  74.         clock_t tStart = clock();
  75.         freopen("input.txt", "r", stdin);
  76.         freopen("output.txt", "w", stdout);
  77.     #endif
  78.  
  79.     sieve();
  80.  
  81.     int t, cs = 0; scanf("%d", &t);
  82.  
  83.     while(t--){
  84.         ll n; scanf("%lld", &n);
  85.         printf("Case %d: %lld\n", ++cs, getcount(n));
  86.     }
  87.  
  88.     #ifdef ERFANUL007
  89.         fprintf(stderr, ">>> Runtime : %.9f\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
  90.     #endif
  91.  
  92.     return 0;
  93. }
RAW Paste Data