fork download
copy 
  1. // Made by Daniel Diaz (@Danidiaztech)
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. /*
  6. Use with caution, may cause precision errors
  7. with floats
  8. */
  9. #pragma GCC optimize ("O3")
  10. #pragma GCC target ("sse4")
  11. #pragma GCC target ("avx,tune=native")
  12.  
  13. #define ll long long
  14.  
  15. const int mod = 1e9 + 7;
  16. const string yes = "YES", no = "NO";
  17.  
  18. const int N = 1e6;
  19. int phi[N + 1];
  20. ll dp[N + 1];
  21.  
  22. int main() {
  23.   cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  24.  
  25.   #if LOCAL
  26.     freopen("input.txt", "r", stdin);
  27.     freopen("output.txt", "w", stdout);
  28.   #endif
  29.  
  30.   for (int i = 0;i <= N; i++){
  31.     phi[i] = i;
  32.   }
  33.  
  34.   for (int i = 2; i <= N; i++){
  35.     if (phi[i] == i){
  36.       for (int j = i; j <= N; j+=i){
  37.         phi[j] -= phi[j] / i;
  38.       }
  39.     }
  40.     // Compute dpi
  41.     dp[i] = dp[i - 1];
  42.  
  43.     for (int d = 1; d * d <= i; d++){
  44.       if (i % d == 0){
  45.         dp[i] += phi[i / d] * d;
  46.         if (d * d != i && d != 1){
  47.           dp[i] += phi[d] * (i / d);
  48.         }
  49.       }
  50.     }
  51.   }
  52.  
  53.   int n; 
  54.   while (cin >> n){
  55.     if (n == 0) break;
  56.     cout << dp[n] << '\n';
  57.   }
  58.  
  59. }
  60.  
Success #stdin #stdout 3s 15184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YF2Npz
problem GCDEX, based on SPOJ submission 32959597 (CPP14), 2024-04-24 01:01:15
language:
C++14 (gcc 8.3)
created:
10 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!