DuongNhi99

PAIRS

Apr 15th, 2022
1,124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int maxN = 1e7 + 5;
  7. const int INF = 1e9 + 7;
  8.  
  9. int main() {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.  
  13.     ll n, m; cin >> n >> m;
  14.  
  15.     vector<ll> p(n + 1);
  16.     for (int i = 1; i <= n; i++)
  17.         p[i] = i;
  18.     for (int i = 2; i*i <= n; i++)
  19.         for (int j = i*i; j <= n; j += i*i)
  20.             p[j] = j / (i*i);
  21.  
  22.     vector<ll> cnt(n + 1);
  23.     for (int i = 1; i <= n; ++i)
  24.         cnt[p[i]]++;
  25.  
  26.     ll ans = 0;
  27.     ll l = 1, r = n;
  28.     while (l <= r) {
  29.         if (l * r <= m) {
  30.             ans += cnt[p[l]] - 1;
  31.             --cnt[p[l]], ++l;
  32.         }
  33.         else --cnt[p[r]], --r;
  34.     }
  35.     cout << ans << '\n';
  36.  
  37.     return 0;
  38. }
  39.  
Advertisement
Add Comment
Please, Sign In to add comment