fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. const int N = 1e7 + 10;
  6. int spf[N];
  7. long long cntspf[N];
  8. int phi[N];
  9. bool invalid[N];
  10. void pre(){
  11. 	for(int i = 2; i * i < N; i++){
  12. 		if(!spf[i]){
  13. 			for(int j = i * i; j < N; j += i)
  14. 				if(!spf[j])
  15. 					spf[j] = i;
  16. 		}
  17. 	}
  18. 	for(int i = 2; i < N; i++) if(!spf[i])
  19. 		spf[i] = i;
  20. 	phi[1] = 1;
  21. 	for(int i = 2; i < N; i++){
  22. 		int p = spf[i];
  23. 		if(p == i){
  24. 			phi[i] = i - 1;
  25. 			continue;
  26. 		}
  27. 		int x = i / p;
  28. 		if(x % p == 0) phi[i] = phi[x] * p;
  29. 		else phi[i] = phi[x] * (p - 1);
  30. 	}
  31. }
  32.  
  33. int main(){
  34. 	pre();
  35. 	int n;
  36. 	cin >> n;
  37. 	long long x = 0;
  38. 	long long disconnected = 1;
  39. 	invalid[1] = 1;
  40. 	for(int i = 1; i <= n; i++){
  41. 		if(2 * spf[i] > n && spf[i] == i){
  42. 			disconnected++;
  43. 			invalid[i] = 1;
  44. 		}
  45. 	}
  46. 	long long valid = n - disconnected;
  47. 	long long paths = (n * 1ll * (n - 1)) / 2;
  48. 	long long P= paths;
  49. 	long long ans = 0;
  50. 	for(int i = 2; i <= n; i++){
  51. 		paths -= phi[i];
  52. 	}
  53.  
  54. 	ans += paths; // dist = 1
  55. 	// spf[i] * spf[j] <= n
  56. 	for(int i = 2; i <= n; i++){
  57. 		cntspf[spf[i]]++;
  58. 	}
  59.  
  60. 	for(int i = 2; i <= n; i++)
  61. 		cntspf[i] += cntspf[i - 1];
  62. 	ll sm = 0;
  63. 	for(int i = 2; i <= n; i++){
  64. 		sm += cntspf[n / spf[i]];
  65. 		sm -= (spf[i] * 1ll * spf[i] <= n);
  66. 	}	
  67.  
  68. 	ans += (sm / 2 - paths) * 2;
  69. 	ans += ((valid * (valid - 1)) / 2 - sm / 2) * 3;
  70. 	cout << ans;
  71.  
  72. 	// cerr << clock() / (double) CLOCKS_PER_SEC << endl;
  73. }
Success #stdin #stdout 0.28s 181248KB
comments (?)
stdin
copy 
10000000
stdout
copy 
75159514333647
https://ideone.com/zhg7gR
language:
C++14 (gcc 8.3)
created:
6 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!