fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 1000000;
  9.  
  10. int n;
  11. ll phi[maxn + 10];
  12.  
  13. void sieve(const int N = maxn)
  14. {
  15.     for (int i = 2; i <= N; i++)
  16.         phi[i] = i;
  17.     for (int i = 2; i <= N; i++)
  18.         if (phi[i] == i)
  19.             for (int j = i; j <= N; j += i)
  20.                 phi[j] -= phi[j]/i;
  21. }
  22. ll sigma(ll a, ll b)
  23. {
  24.     return (b - a + 1) * (a + b) >> 1;
  25. }
  26.  
  27. int main()
  28. {
  29.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  30.     if (fopen("GCD_EXTREME.INP", "r"))
  31.     {
  32.         freopen("GCD_EXTREME.INP", "r", stdin);
  33.         freopen("GCD_EXTREME.OUT", "w", stdout);
  34.     }
  35.  
  36.     sieve();
  37.  
  38.     for (int i = 1; i <= maxn; i++)
  39.         phi[i] += phi[i - 1];
  40.  
  41.     while (cin >> n)
  42.     {
  43.         if (n == 0) break;
  44.         ll ans = 0;
  45.         int last = 1;
  46.  
  47.         while (1)
  48.         {
  49.             ll d = n/last;
  50.             int nx = n/d;
  51.  
  52.             ans += (phi[d]) * sigma(last, nx);
  53.  
  54.             last = nx + 1;
  55.             if (nx >= n) break;
  56.         }
  57.         cout << ans, el;
  58.     }
  59. }
  60.  
Success #stdin #stdout 0.09s 11380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZzW5JW
language:
C++14 (gcc 8.3)
created:
6 days 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!