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