fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct MillerRabin {
  6.     typedef long long ll;
  7.  
  8.     ll mulMod(ll a, ll b, ll mod) {
  9.         return __int128_t(a) * b % mod; 
  10.     }
  11.  
  12.     ll power(ll b, ll e, ll mod) {
  13.         ll ans = 1;
  14.         for (; e > 0; e >>= 1, b = mulMod(b, b, mod))
  15.             if (e & 1) ans = mulMod(ans, b, mod);
  16.         return ans;
  17.     }
  18.  
  19.     pair<ll, ll> factorie(ll x) {
  20.         ll cnt = 0;
  21.         for (; x % 2 == 0; x /= 2) cnt++;
  22.         return {x, cnt};
  23.     }
  24.  
  25.     bool test_a(ll a, ll s, ll m, ll n) {
  26.         if (n == a) return true;
  27.         ll x = power(a, m, n);
  28.         if (x == 1) return true;
  29.         while (s--) {
  30.             if (x == n - 1) return true;
  31.             x = mulMod(x, x, n); 
  32.             if (x == 1) return false;
  33.         }
  34.         return false;
  35.     }
  36.  
  37.     bool isPrime(ll n) {
  38.         if (n < 2) return false;
  39.         if (n == 2 || n == 3 || n == 5 || n == 7) return true;
  40.         if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) return false;
  41.         if (n < 121) return n > 1;
  42.  
  43.         ll s = 0, m = n - 1;
  44.         for (; m % 2 == 0; m /= 2) s++;
  45.  
  46.         if (n < (1ull << 32)) {
  47.             for (ll a: {2, 7, 61}) 
  48.                 if (!test_a(a, s, m, n)) return false;
  49.         }
  50.         else {
  51.             for (ll a: {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) 
  52.                 if (!test_a(a, s, m, n)) return false;
  53.         }
  54.         return true;
  55.     }
  56. };
  57.  
  58. void Task() {
  59.     if (fopen("test.inp", "r")) {
  60.         freopen("test.inp", "r", stdin);
  61.         freopen("test.out", "w", stdout);
  62.     }
  63. }
  64.  
  65. void Solve() {
  66.     vector <int> vecPrime(1e7, true);
  67.     for (int i = 2; i * i <= 1e7; ++i) {
  68.         if (vecPrime[i] == true) {
  69.             for (int j = i * i; j <= 1e7; j += i) {
  70.                 vecPrime[j] = false;
  71.             }
  72.         }
  73.     }
  74.     vector <int> vecP;
  75.     for (int i = 2; i <= 1e7; ++i) {
  76.         if (vecPrime[i] == true) {
  77.             vecP.push_back(i);
  78.         }
  79.     }
  80.     long long n; cin >> n;
  81.     long long ans = 1;
  82.     for (auto p : vecP) {
  83.         if (1LL * p * p * p > n) {
  84.             break;
  85.         }
  86.         int cnt = 0;
  87.         while (n % p == 0) {
  88.             cnt++;
  89.             n /= p;
  90.         }
  91.         ans *= 1LL * (cnt + 1);
  92.     }
  93.     MillerRabin MR;
  94.     if (MR.isPrime(n) == true) {
  95.         ans *= 2;
  96.     } else {
  97.         long long m = sqrt(n);
  98.         if (m * m == n && MR.isPrime(m) == true) {
  99.             ans *= 3;
  100.         } else if (n != 1) {
  101.             ans *= 4;
  102.         }
  103.     }
  104.     cout << ans;
  105. }
  106.  
  107. int main() {
  108.     ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
  109.     Task();
  110.     Solve();
  111. }
  112.  
Success #stdin #stdout 0.16s 47096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
https://ideone.com/Mn1Jgu
language:
C++14 (gcc 8.3)
created:
1 day 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!