fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long ans = 0;
  6. const int maxn = 1e6 + 6;
  7. long long primes[maxn];
  8. long long d[1000];
  9. int size_d = 0;
  10. long long dd[1000][2];
  11. int cur_d = 0;
  12. long long tmpans = 0;
  13. long long bound = 0;
  14.  
  15. void rec(int pos, long long mask, int sign)
  16. {
  17.     if (pos == cur_d) {
  18.         tmpans += sign * (bound / mask);
  19.         return;
  20.     }
  21.     int tmp = 1;
  22.     int si = 1;
  23.     for (int i = 0; i <= 1; i++) {
  24.         rec(pos + 1, mask * tmp, sign * si);
  25.         si = -si;
  26.         tmp = tmp * dd[pos][0];
  27.     }
  28. }
  29.  
  30. long long solve(int p, int r)
  31. {
  32.     if (p == 1)
  33.         return r;
  34.     bound = r;
  35.     int size_d = 0;
  36.     while (primes[p] != 1)
  37.     {
  38.         d[size_d++] = primes[p];
  39.         p /= primes[p];
  40.     }
  41.     sort(d, d + size_d);
  42.     dd[0][0] = d[0];
  43.     dd[0][1] = 1;
  44.     cur_d = 1;
  45.     for (int i = 1; i < size_d; i++)
  46.     {
  47.         if (d[i] == d[i - 1])
  48.         {
  49.             dd[cur_d - 1][1]++;
  50.         } else
  51.         {
  52.             dd[cur_d][0] = d[i];
  53.             dd[cur_d][1] = 1;
  54.             cur_d++;
  55.         }
  56.     }
  57.     tmpans = 0;
  58.     rec(0, 1, 1);
  59.     return tmpans;
  60. }
  61.  
  62. int main()
  63. {     
  64.     int n = 0;
  65.     cin >> n;
  66.     int m = sqrt(n);
  67.     for (int i = 1; i <= m; i++)
  68.         primes[i] = i;
  69.     for (int i = 2; i * i <= m; i++)
  70.     {
  71.         if (primes[i] == i)
  72.         {
  73.             for (int j = i * i; j <= m; j += i)
  74.                 primes[j] = i;
  75.         }
  76.     }
  77.     ans = 0;
  78.     for (int i = 2; i * i < n; i++) {
  79.         int r = n / i;
  80.         ans += solve(i, r) - solve(i, i);
  81.     }
  82.     cout << ans << endl;
  83.     return 0;
  84. }
Success #stdin #stdout 0s 11312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/7619Do
language:
C++14 (gcc 8.3)
created:
7 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!