fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define math signed main()
  4. #define int long long
  5. int n, ans = 1;
  6.  
  7. void pt(int x)
  8. {
  9.     if (n % x != 0) return;
  10.     int cnt = 0;
  11.     while (n % x == 0) cnt++, n /= x;
  12.     ans *= (cnt + 1);
  13. }
  14.  
  15. int mulmod(int x, int n, int m)
  16. {
  17.     int a = 0;
  18.     x %= m;
  19.     for (; n; n >>= 1, x = x * 2 % m)
  20.         if (n & 1)
  21.             (a += x) %= m;
  22.     return a;
  23. }
  24. int power(int x, int n, int m)
  25. {
  26.     int a = 1;
  27.     x %= m;
  28.     for (; n; n >>= 1, x = mulmod(x, x, m))
  29.     if (n & 1) a = mulmod(a, x, m);
  30.     return a;
  31. }
  32. bool check(int a, int n, int m, int k)
  33. {
  34.     int t = power(a, m, n);
  35.     if (t == 1 || t == n - 1) return false;
  36.     for (int i = 1; i < k; i++)
  37.     {
  38.         t = mulmod(t, t, n);
  39.         if (t == n - 1) return false;
  40.     }
  41.     return true;
  42. }
  43. bool miller(int n)
  44. {
  45.     if (n < 2) return false;
  46.     if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0)
  47.     return n == 2 || n == 3 || n == 5 || n == 7;
  48.     int m = n - 1, k = 0;
  49.     while ((m & 1) == 0)
  50.     m >>= 1, k++;
  51.     for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37})
  52.     {
  53.         if (a > n - 2) break;
  54.         if (check(a, n, m, k)) return false;
  55.     }
  56.     return true;
  57. }
  58. math
  59. {
  60.     cin.tie(0)->sync_with_stdio(0);
  61.     cin >> n;
  62.     if (miller(n)) return cout << 2,0;
  63.     pt(2);
  64.     pt(3);
  65.     for (int i = 5; i * i * i <= n; i += 6) {
  66.         pt(i);
  67.         pt(i + 2);
  68.     }
  69.     if (miller(n))
  70.         ans *= 2;
  71.     else {
  72.         int a = sqrt(n);
  73.         if (a * a == n && miller(a))
  74.             ans *= 3;
  75.         else
  76.             ans *= 4;
  77.     }
  78.     cout << ans << "\n";
  79.     return 0;
  80. }
Time limit exceeded #stdin #stdout 5s 5264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vJijKn
language:
C++14 (gcc 8.3)
created:
87 days 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!