fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. ll prime[1000005];
  6. ll arr[1000005];
  7.  
  8.  
  9. ll mulmod(ll a, ll b, ll c)
  10. {
  11.     ll x = 0, y = a % c;
  12.     while (b)
  13.     {
  14.         if (b & 1)
  15.             x = (x + y) % c;
  16.         y = (y << 1) % c;
  17.         b >>= 1;
  18.     }
  19.     return x % c;
  20. }
  21. ll fastPow(ll x, ll n, ll MOD)
  22. {
  23.     ll ret = 1;
  24.     while (n)
  25.     {
  26.         if (n & 1)
  27.             ret = mulmod(ret, x, MOD);
  28.         x = mulmod(x, x, MOD);
  29.         n >>= 1;
  30.     }
  31.     return ret % MOD;
  32. }
  33. bool isPrime(ll n)
  34. {
  35.     if(n == 2 || n == 3)
  36.         return true;
  37.     if(n == 1 || !(n & 1))
  38.         return false;
  39.     ll d = n - 1;
  40.     int s = 0;
  41.     while (d % 2 == 0)
  42.     {
  43.         s++;
  44.         d /= 2;
  45.     }
  46.     int a[9] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
  47.     for(int i = 0; i < 9; i++)
  48.     {
  49.         if(n == a[i])
  50.             return true;
  51.         bool comp = fastPow(a[i], d, n) != 1;
  52.         if(comp)
  53.             for(int j = 0; j < s; j++)
  54.             {
  55.                 ll fp = fastPow(a[i], (1LL << (ll)j)*d, n);
  56.                 if (fp == n - 1)
  57.                 {
  58.                     comp = false;
  59.                     break;
  60.                 }
  61.             }
  62.         if(comp)
  63.             return false;
  64.     }
  65.     return true;
  66. }
  67.  
  68.  
  69. void prime_gen()
  70. {
  71.  
  72.     for(ll i=4; i<=1000000; i+=2)
  73.         arr[i]=1;
  74.  
  75.     for(ll i=3; i*i<=1000000; i+=2)
  76.     {
  77.         if(arr[i]==0)
  78.         {
  79.             for(ll j=i*i; j<=1000000; j+=2*i)
  80.             {
  81.                 arr[j]=1;
  82.             }
  83.         }
  84.     }
  85.     prime[0]=2;
  86.     ll j;
  87.     for(ll i=3,j=1; i<=1000000; i+=2)
  88.     {
  89.         if(arr[i]==0)
  90.         {
  91.             prime[j++]=i;
  92.         }
  93.     }
  94.     return;
  95. }
  96.  
  97.  
  98. int main()
  99. {
  100.     prime_gen();
  101.     ll i,j,n,m,t;
  102.     scanf("%lld",&t);
  103.  
  104.     for(ll tes=0; tes<t; tes++)
  105.     {
  106.         scanf("%lld",&n);
  107.         ll cnt=0,ans=1;
  108.         for(i=0;; i++)
  109.         {
  110.             cnt=0;
  111.             if(prime[i]!=0&&prime[i]*prime[i]*prime[i]<=n)
  112.             {
  113.                 while(n%prime[i]==0)
  114.                 {
  115.                     n/=prime[i];
  116.                     cnt++;
  117.                 }
  118.                 ans*=(cnt+1);
  119.             }
  120.             else
  121.                 break;
  122.         }
  123.         ll y=sqrt(n*1.0);
  124.         if(isPrime(n))
  125.         {
  126.             ans*=2;
  127.         }
  128.         else if(isPrime(y)&&y*y==n)
  129.         {
  130.             ans*=3;
  131.         }
  132.         else if(n!=1)
  133.         {
  134.             ans*=4;
  135.         }
  136.  
  137.         cout<<ans<<endl;
  138.     }
  139.     return 0;
  140. }
  141.  
Success #stdin #stdout 0.01s 12000KB
comments (?)
stdin
copy 
3
6 24 100
stdout
copy 
4
8
9
https://ideone.com/dBRF7u
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!