fork download
  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
stdin
Standard input is empty
stdout
0