Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- const int maxN = 1e7 + 5;
- const int INF = 1e9 + 7;
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- ll n, m; cin >> n >> m;
- vector<ll> p(n + 1);
- for (int i = 1; i <= n; i++)
- p[i] = i;
- for (int i = 2; i*i <= n; i++)
- for (int j = i*i; j <= n; j += i*i)
- p[j] = j / (i*i);
- vector<ll> cnt(n + 1);
- for (int i = 1; i <= n; ++i)
- cnt[p[i]]++;
- ll ans = 0;
- ll l = 1, r = n;
- while (l <= r) {
- if (l * r <= m) {
- ans += cnt[p[l]] - 1;
- --cnt[p[l]], ++l;
- }
- else --cnt[p[r]], --r;
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment