fork download
copy 
  1. #pragma GCC optimize("Ofast")  
  2. #pragma GCC target("avx,avx2,fma")
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. #define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  6. #define int long long 
  7. #define endl "\n"
  8. #define all(x) (x).begin(),(x).end()
  9. const int MOD = 1e9+7;
  10. const int mxN = 1e6+3;
  11.  
  12. int phi[mxN+1]; 
  13. // This is my previously implemented function, I hope there is no mistake in this
  14. void computeTotient(int n){  
  15.     for (int i=1; i<=n; i++) 
  16.         phi[i] = i; 
  17.     for (int p=2; p<=n; p++){ 
  18.         if (phi[p] == p) { 
  19.             phi[p] = p-1; 
  20.             for (int i = 2*p; i<=n; i += p){ 
  21.                phi[i] = (phi[i]/p) * (p-1); 
  22.             } 
  23.         } 
  24.     }
  25. }
  26.  
  27. int32_t main(){
  28.     IO;
  29.  
  30.     int nT = 1;
  31.     cin >> nT;
  32.     int val[nT];
  33.     int mx = 0;
  34.     for(int i = 0; i < nT; ++i){
  35.         cin >> val[i];
  36.         mx = max(mx, val[i]);
  37.     }
  38.     computeTotient(mx + 1);
  39.     for(int i = 2; i <= mx; ++i){
  40.         phi[i] += phi[i - 1];
  41.     }
  42.     int ans = 0;
  43.     // I used #define , so all int(s) are actually long long(s). Rather than doing -1 every time , I did -nT after for loop
  44.     int countzeroes = 0;
  45.     for(int i = 0; i < nT; ++i){
  46.         if(val[i] == 0)countzeroes++;
  47.         ans += (2ll * phi[val[i]]);
  48.     }
  49.     ans -= nT;
  50.     ans += countzeroes;
  51.     cout << ans << endl;
  52.     return 0;
  53. }
  54.  
Runtime error #stdin #stdout 0s 4264KB
comments (?)
stdin
copy 
3
1 3 4
stdout
copy 
Standard output is empty
https://ideone.com/gJjL4C
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!