azizulhaquealif

1028 – Trailing Zeroes (I)

Sep 28th, 2020
976
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> pii;
  7. typedef pair<ll, ll> pll;
  8. #define all(x) (x).begin(), (x).end()
  9. #define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  10. const ll INF = 2000000000000000000LL;
  11. const int inf = 0x3f3f3f3f;
  12. const long double EPS = 1e-9;
  13. #define Read()  freopen("D://Input.txt", "r", stdin);
  14. #define Write() freopen("D://Output.txt", "w", stdout);
  15.  
  16. int lp[1234567], SSize = 1000000;
  17. vector<int>primes;
  18. void Sieve(){
  19.     for(int i = 2; i <= SSize; i++){
  20.         if(lp[i] == 0){
  21.             lp[i] = i;
  22.             primes.push_back(i);
  23.         }
  24.         for(int j = 0; j < (int)primes.size() && primes[j] <= lp[i] && i*primes[j] <= SSize; j++)
  25.             lp[i*primes[j]] = primes[j];
  26.     }
  27. }
  28.  
  29. int divisorCount(ll n){
  30.     int ans = 1;
  31.     for(int i = 0; i < (int)primes.size(); i++){
  32.         int p = primes[i];
  33.         if(p*p*p > n)break;
  34.         int count = 1;
  35.         while(n % p == 0){
  36.             n /= p;
  37.             count++;
  38.         }
  39.         ans *= count;
  40.     }
  41.  
  42.     ll sq = sqrt(n);
  43.     //cout<<sq<<endl;
  44.  
  45.     if(lp[n] == n)ans *= 2;
  46.     else if(sq*sq == n && lp[sq] == sq)ans *= 3;
  47.     else if(n != 1)ans *= 4;
  48.     return ans;
  49. }
  50.  
  51. int main(){FastIO;
  52.     Read(); Write();
  53.     Sieve();
  54.  
  55.     int t, cas = 0;
  56.     scanf("%d", &t);
  57.  
  58.     while(t--){
  59.         ll n;
  60.         scanf("%lld", &n);
  61.  
  62.         printf("Case %d: ", ++cas);
  63.         if(n == 1){
  64.             printf("0\n");
  65.             continue;
  66.         }
  67.  
  68.         int ans = divisorCount(n);
  69.         printf("%d\n", ans-1);
  70.     }
  71.  
  72.     return 0;
  73. }
RAW Paste Data