fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. vector<int> prime, lpf;
  8. void sieve(int n)
  9. {
  10.     prime.assign(1, 2);
  11.     lpf.assign(n + 1, 2);
  12.  
  13.     for (int x = 3; x <= n; x += 2)
  14.     {
  15.         if (lpf[x] == 2) prime.push_back(lpf[x] = x);
  16.         for (int i = 0; i < prime.size() && prime[i] <= lpf[x] && prime[i] * x <= n; ++i)
  17.             lpf[prime[i] * x] = prime[i];
  18.     }
  19. }
  20.  
  21. ll addMOD(ll a, ll b, const ll MOD)
  22. {
  23.     return (a + b) % MOD;
  24. }
  25.  
  26. ll mulMOD(ll a, ll b, const ll MOD)
  27. {
  28.     // if (double(a) * b <= 1e18) return (a * b) % MOD;
  29.  
  30.     ll res = 0;
  31.     for (a %= MOD; b > 0; a <<= 1, b >>= 1)
  32.     {
  33.         if (a >= MOD) a -= MOD;
  34.         if (b & 1) 
  35.         {
  36.             res += a;
  37.             if (res >= MOD) res -= MOD;
  38.         }
  39.     }
  40.  
  41.     return res;
  42. }
  43.  
  44. ll powMOD(ll x, ll n, const ll MOD)
  45. {
  46.     ll res = 1;
  47.     for (; n > 0; n >>= 1)
  48.     {
  49.         if (n & 1) res = mulMOD(res, x, MOD);
  50.         x = mulMOD(x, x, MOD);
  51.     }
  52.  
  53.     return res;
  54. }
  55.  
  56. bool mr_test(ll n, int a, ll d, int s)
  57. {
  58.     ll x = powMOD(a, d, n);
  59.     if (x == 1 || x == n - 1) return false;
  60.  
  61.     for (int r = 1; r < s; ++r)
  62.     {
  63.         x = mulMOD(x, x, n);
  64.         if (x == n - 1) return false;
  65.     }
  66.  
  67.     return true;
  68. }
  69.  
  70. bool miller_rabin(ll n, int k = 5)
  71. {
  72.     if (n < 4) return n == 2 || n == 3;
  73.     if (n % 2 == 0 || n % 3 == 0) return false;
  74.  
  75.     int s = __builtin_ctz(n - 1);
  76.     ll d = (n - 1) >> s;
  77.     for (int it = 1; it <= 5; ++it)
  78.     {
  79.         int a = 2 + rand() % (n - 3);
  80.         if (mr_test(n, a, d, s)) return false;
  81.     }
  82.  
  83.     return true;
  84. }
  85.  
  86. bool isPrime(ll n)
  87. {
  88.     if (n < 2) return false;    
  89.     if (n < lpf.size()) return lpf[n] == n;
  90.     return miller_rabin(n);
  91. }
  92.  
  93. ll any_divisor_of(ll n)
  94. {
  95.     if (n <= 1) return 1;
  96.     if (n < lpf.size()) return lpf[n];
  97.     if (isPrime(n)) return n;
  98.  
  99.     ll d = n;
  100.     for (ll c = 2; d == n; ++c)
  101.     {    
  102.         ll x = 2, y = 2, i = 2, k = 2;
  103.         while (true)
  104.         {
  105.             x = (mulMOD(x, x, n) + c);
  106.             if (x >= n)	x -= n;
  107.             d = __gcd(abs(x - y), n);
  108.             if (d > 1 && n % d == 0) break;
  109.             if (i++ == k) y = x, k <<= 1;
  110.         }
  111.     }
  112.  
  113.     return d;
  114. }
  115.  
  116. bool isSquarePrime(ll n)
  117. {
  118.     ll t = round(sqrt(n));
  119.     return (t * t == n && isPrime(t));
  120. }
  121.  
  122. bool isCubePrime(ll n)
  123. {
  124.     ll t = round(cbrt(n));
  125.     return (t * t * t == n && isPrime(t));
  126. }
  127.  
  128. bool isSemiPrime(ll n)
  129. {
  130.     ll d = any_divisor_of(n);
  131.     return isPrime(d) && isPrime(n / d);
  132. }
  133.  
  134. bool isSphenicPrime(ll n)
  135. {
  136.     ll p = any_divisor_of(n);       n /= p;
  137.     if (isPrime(n)) swap(p, n);
  138.  
  139.     ll q = any_divisor_of(n);       n /= q;
  140.     return (p != q) && (q != n) && (n != p) && isPrime(p) && isPrime(q) && isPrime(n);
  141. }
  142.  
  143. ll d(ll n)
  144. {   
  145.     int t = sqrt(sqrt(n)) + 1;
  146.     sieve(t);
  147.  
  148.     ll res = 1;
  149.     for (int p : prime)
  150.     {
  151.         if (1LL * p * p * p * p > n) break;
  152.         if (n % p == 0)
  153.         {
  154.             int f = 0;
  155.             do ++f; while ((n /= p) % p == 0);
  156.             res *= (f + 1);
  157.         }
  158.     }
  159.  
  160.     if (n == 1) return res;
  161.     if (isPrime(n)) return res * 2;
  162.     if (isSquarePrime(n)) return res * 3;
  163.     if (isSemiPrime(n)) return res * 4;
  164.     if (isCubePrime(n)) return res * 4;
  165.     if (isSphenicPrime(n)) return res * 8;
  166.     return res * 6;
  167. }
  168.  
  169. int main()
  170. {
  171.     srand(time(NULL));
  172.  
  173.     ll n;
  174.     cin >> n;
  175.  
  176.     cout << d(n);
  177.     return 0;
  178. } 
  179.  
  180. /// N = X * Y
  181. /// K = N^(1/4)
  182. /// X <= K
  183. ///
  184. /// for a, b, c distint prime
  185. /// > Y = a
  186. ///
  187. /// > Y = a^2
  188. /// > Y = a * b
  189. ///
  190. /// > Y = a^3
  191. /// > Y = a^2 * b
  192. /// > Y = a * b * c
Success #stdin #stdout 0.01s 5528KB
comments (?)
stdin
copy 
3333333333333333
stdout
copy 
128
https://ideone.com/yiu8Pt
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!