fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define MAX 1000000
  4. #define deb(x) cout << #x << "=" << x << endl;
  5. using namespace std;
  6.  
  7. vector<int> phi(MAX + 5);
  8.  
  9. signed main() {
  10.     phi[1] = 1;
  11.     int i,j;
  12.     for( i=0;i<MAX;i++)phi[i]=i;
  13.     for( i=2;i<MAX;i++){
  14.         if(phi[i]==i){
  15.             for(j=i;j<MAX;j+=i){
  16.                 phi[j]-=phi[j]/i;
  17.             }
  18.         }
  19.     }
  20.         int sum = 0;
  21.     for (int i = 1; i <= MAX; i++) {
  22.         sum += phi[i];
  23.         phi[i] = sum;
  24.         phi[i] = (2LL * phi[i]) - 1;
  25.     }
  26.     long long q, ans = 0;
  27.     cin >> q;
  28.     while (q--) {
  29.         int n;
  30.         cin >> n;
  31.         int temp = phi[n];
  32.         ans += temp;
  33.     }
  34.     cout << ans;
  35.  
  36.     return 0;
  37. }
Success #stdin #stdout 0.06s 11028KB
comments (?)
stdin
copy 
3
1 3 4
stdout
copy 
19
https://ideone.com/1KgpIk
language:
C++14 (gcc 8.3)
created:
4 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!