fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define PB push_back
  5. #define FI first
  6. #define SE second
  7. #define PI pair<int,int>
  8. #define MP make_pair
  9. #define Aint(DATAST) DATAST.begin(), DATAST.end()
  10. #define MOD 1000000007
  11. #define SIZE 10000001
  12.  
  13. int tot[SIZE];
  14. int ans[SIZE];
  15.  
  16. int main()
  17. {
  18.     ios::sync_with_stdio(0);
  19.     cin.tie(0); cout.tie(0);
  20. #ifndef ONLINE_JUDGE
  21.     freopen("input.txt", "r", stdin);
  22.     freopen("output.txt", "w", stdout);
  23. #endif
  24.  
  25.     for (ll i = 0; i < SIZE; i++)
  26.         tot[i] = i;
  27.  
  28.     for (ll i = 2; i < SIZE; i++)
  29.     {
  30.         if (tot[i] == i)
  31.         {
  32.             for (ll j = i; j < SIZE; j += i)
  33.                 tot[j] -= tot[j] / i;
  34.         }
  35.     }
  36.  
  37.     memset(ans, 0, sizeof(ans));
  38.  
  39.     for (ll i = 1; i < SIZE; i++)
  40.     {
  41.         for (ll j = i; j < SIZE; j += i)
  42.             ans[j] += (tot[i] * i);
  43.     }
  44.  
  45.     int t, n;
  46.     cin >> t;
  47.  
  48.  
  49.     while (t--)
  50.     {
  51.         cin >> n;
  52.         cout << ans[n] << endl;
  53.     }
  54.  
  55.  
  56.     return 0;
  57. }
Success #stdin #stdout 2.04s 81604KB
comments (?)
stdin 
5
1
2
3
4
5
stdout 
1
3
7
11
21
https://ideone.com/PG57Ir
language:
C++14 (gcc 8.3)
created:
4 years 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!