fork download
  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
stdin
3
1 3 4
stdout
Standard output is empty