Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using i64 = int64_t;
- using i128 = __int128;
- int main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- i64 N, M; cin >> N >> M;
- /// f(x) - f(x-1) = 2x-1 - sigma_1(x) ///
- auto f = [&](i128 x) -> i128 {
- /// find sum of (x mod i) = x - (x / i) * i ///
- i128 ans = x * x, i = 1;
- while (i <= x) {
- /// [x/j == x/i] --> [(x+1)/(x/i) < j <= x/(x/i)] ///
- i128 r = min(x / (x / i), x);
- ans -= (x / i) * (i + r) * (r - i + 1) / 2;
- i = r + 1;
- }
- return ans;
- };
- i64 lo = 0, hi = N, mi;
- while (lo < hi) {
- mi = (lo + hi + 1) >> 1;
- if (f(mi) <= M) lo = mi;
- else hi = mi - 1;
- }
- i64 ans = lo;
- for (int d = 1; d <= 5; ++d) {
- if (lo + d <= N and f(lo+d) <= M) ++ans;
- if (lo - d >= 1 and f(lo-d) > M) --ans;
- }
- cout << ans << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement