fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #define LL long long
  5. #define MAXN 1000003
  6. using namespace std;
  7.  
  8. bool is_prime[MAXN] = {false};
  9. vector<LL> primes;
  10.  
  11. void sieve_eratosthenes()
  12. {
  13.   for(int i = 0; i < MAXN; i++)
  14.       is_prime[i] = true;
  15.   is_prime[0]=false;
  16.   is_prime[1] = false;
  17.   for(int i = 2; i*i <= MAXN; i++)
  18.   {
  19.     if(is_prime[i])
  20.     {
  21.       for(int j = 2*i; j <= MAXN; j += i)
  22.       {
  23.         is_prime[j] = false;
  24.       }
  25.     }
  26.   }
  27.   for(int i = 2; i < MAXN; i++)
  28.       if(is_prime[i])
  29.         primes.push_back(i);
  30. }
  31.  
  32. inline LL multiply(LL a, LL b, const LL &m)
  33. {
  34.   a %= m, b %= m;
  35.   long double res = a;res = b;
  36.   LL c = (LL)(res/m);
  37.   a = b;
  38.   a -= c*m;
  39.   a %= m;
  40.   if(a < 0)
  41.     a+= m;
  42. return a;
  43. }
  44.  
  45. inline LL power(LL a, LL b, const LL &m)
  46. {
  47.   LL ans = 1;
  48.   while(b)
  49.   {
  50.     if(b & 1)
  51.     {
  52.       ans = multiply(ans, a, m);
  53.     }
  54.     a = multiply(a, a, m);
  55.     b >>= 1;
  56.   }
  57.   return ans;
  58. }
  59.  
  60. // Returns true if p is prime
  61. inline bool Miller(LL p)
  62. {
  63.   if(p < 2)
  64.     return false;
  65.   if(p != 2 && !(p&1))
  66.     return false;
  67.   int cnt = 0;
  68.   LL s = p-1;
  69.   while(!(s&1))
  70.   {
  71.     s /= 2;
  72.     cnt++;
  73.   }
  74.   LL accuracy = 2, m;
  75.   for(int i = 0; i < accuracy; i++)
  76.   {
  77.     LL a = rand() % (p-1) + 1;
  78.     m = p;
  79.     LL x = power(a, s, m);
  80.     if(x == 1 || x == p-1)
  81.       continue;
  82.     int flag = 0;
  83.     for(int i = 1; i < cnt; i++)
  84.     {
  85.       x = multiply(x, x, m);
  86.       if(x == 1)
  87.         return false;
  88.       if(x == p-1)
  89.       {
  90.         flag = 1;
  91.         break;
  92.       }
  93.     }
  94.       if(flag)
  95.         continue;
  96.       return false;
  97.     }
  98.     return true;
  99. }
  100.  
  101. LL count_divisors(LL n)
  102. {
  103.   LL ans = 1;
  104.   int sze=primes.size();
  105.   for(int i=0;i<sze;i++)
  106.     {
  107.       LL p=primes[i];
  108.       if(p*p*p > n)
  109.         break;
  110.       LL count = 1;
  111.       while(n % p == 0)
  112.       {
  113.         n /= p;
  114.         count++;
  115.       }
  116.       ans = ans*count; //anscount to ans*count
  117.     }
  118.   LL sq = sqrt(double(n));
  119.   if(Miller(n))
  120.   {
  121.     ans = ans*2; // ans2 to ans*2
  122.   }
  123.   else if(sq*sq == n && Miller(sq)) // sqsq to sq*sq
  124.   {
  125.   ans = 3;
  126.   }
  127.   else if(n != 1)
  128.   {
  129.   ans *= 4;
  130.   }
  131.   return ans;
  132. }
  133.  
  134. int main()
  135. {
  136.   sieve_eratosthenes();
  137.   LL n;
  138.   cin >> n;
  139.   cout << count_divisors(n) << endl;
  140.   return 0;
  141. }
  142.  
Success #stdin #stdout 0s 17040KB
comments (?)
stdin
copy 
11
stdout
copy 
4
https://ideone.com/eBnZ37
language:
C++14 (gcc 8.3)
created:
6 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!