fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5. const int MAXN = (int)1e7 + 42;
  6. const int64_t mod = (int64_t)1e9 + 7;
  7.  
  8. template <class T>
  9. struct fenwick
  10. {
  11. 	int sz;
  12. 	T tr[MAXN];
  13.  
  14. 	void init(int n)
  15. 	{
  16. 		sz = n + 1;
  17. 		memset(tr, 0, sizeof(tr));
  18. 	}
  19.  
  20. 	T query(int idx)
  21. 	{
  22. 		T ans = 0;
  23. 		for(; idx >= 1; idx -= (idx & -idx))
  24. 			ans += tr[idx];
  25. 		return ans;
  26. 	}
  27.  
  28. 	void update(int idx, T val)
  29. 	{
  30. 		if(idx <= 0) return;
  31. 		for(; idx <= sz; idx += (idx & -idx))
  32. 			tr[idx] += val;
  33. 	}
  34.  
  35. 	T query(int l, int r) { return query(r) - query(l - 1); }
  36. };
  37.  
  38.  
  39. int n;
  40.  
  41. void read()
  42. {
  43. 	cin >> n;
  44. }
  45.  
  46. int64_t answer = 0;
  47. int64_t cnt[MAXN], c[MAXN];
  48. int lp[MAXN];
  49.  
  50. int64_t C(int64_t x) { return x * 1ll * (x - 1) / 2ll; }
  51.  
  52. fenwick<int64_t> t;
  53.  
  54. void solve()
  55. {
  56. 	t.init(n);
  57. 	for(int i = 2; i <= n; i++)
  58. 		if(lp[i] == 0) for(int x = i; x <= n; x += i)
  59. 			if(lp[x] == 0) lp[x] = i;
  60.  
  61. 	for(int i = 2; i <= n; i++)
  62. 		cnt[i] += (n - i) / i + 1, c[i] += (n - i) / i + 1;
  63.  
  64. 	for(int i = 2; i <= n; i++)
  65. 		cnt[i] = C(cnt[i]);
  66.  
  67. 	for(int i = n; i >= 1; i--)
  68. 		for(int x = i * 2; x <= n; x += i)
  69. 			cnt[i] -= cnt[x];
  70.  
  71. 	for(int i = 2; i <= n; i++)
  72. 		answer -= cnt[i];
  73.  
  74. 	for(int i = 2; i <= n; i++)
  75. 		t.update(lp[i], 1);
  76.  
  77. 	for(int i = 2; i <= n; i++)
  78. 	{
  79. 		t.update(lp[i], -1);
  80. 		int64_t cnt2 = t.query(n / lp[i]);
  81. 		int64_t cnt3 = t.query(n / 2);
  82.  
  83. 		cnt3 -= cnt2;
  84. 		answer += cnt2 * 2ll;
  85. 		if(lp[i] * 2 <= n) answer += cnt3 * 3ll;
  86. 	}
  87.  
  88. 	cout << answer << endl;
  89. }
  90.  
  91. int main()
  92. {
  93. 	ios_base::sync_with_stdio(false);
  94. 	cin.tie(NULL);
  95.  
  96. 	read();
  97. 	solve();
  98. 	return 0;
  99. }
  100.  
Success #stdin #stdout 0.02s 289472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/oCgfoT
language:
C++ (gcc 8.3)
created:
6 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!