verify/Algorithm_bisect_max_right.test.cpp

View this file on GitHub
Last update: 2025-01-11 20:14:38+09:00
Problem: https://judge.yosupo.jp/problem/enumerate_quotients

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_quotients"
#include "../Utility/template.hpp"
#include "../Algorithm/bisect.hpp"
/*
n/x - n/(x+1) >= 1
⇔
n >= x(x+1)
*/
int main() {
    ll n;
    cin >> n;

    auto pred = [&](ll r) { return n >= __int128_t(r) * (r + 1); };

    ll x = max_right(0LL, n + 1, pred);
    x--;
    vec<ll> ans;
    rep(i, 1, x + 1) ans.push_back(n / i);

    for (ll i = n / (x + 1); i >= 1; i--) ans.push_back(i);

    reverse(all(ans));
    cout << ans.size() << endl;
    rep(i, 0, ans.size()) cout << ans[i] << " ";
}

#line 1 "verify/Algorithm_bisect_max_right.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_quotients"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Algorithm/bisect.hpp"

template <typename T, typename F> T max_right(T l, T max_r_plus_one, F pred) {
    assert(l < max_r_plus_one);

    if (!pred(l)) return l;

    while (max_r_plus_one > l + 1) {
        T mid = ((l ^ max_r_plus_one) >> 1) + (l & max_r_plus_one);
        (pred(mid) ? l : max_r_plus_one) = mid;
    }
    return max_r_plus_one;
};

template <typename T, typename F> T min_left(T min_l, T r, F pred) {
    assert(min_l < r);

    if (pred(min_l)) return min_l;

    while (r > min_l + 1) {
        T mid = ((min_l ^ r) >> 1) + (min_l & r);
        (pred(mid) ? r : min_l) = mid;
    }
    return r;
}
/*
@brief 抽象化二分探索
@docs doc/bisect.md
*/
#line 4 "verify/Algorithm_bisect_max_right.test.cpp"
/*
n/x - n/(x+1) >= 1
⇔
n >= x(x+1)
*/
int main() {
    ll n;
    cin >> n;

    auto pred = [&](ll r) { return n >= __int128_t(r) * (r + 1); };

    ll x = max_right(0LL, n + 1, pred);
    x--;
    vec<ll> ans;
    rep(i, 1, x + 1) ans.push_back(n / i);

    for (ll i = n / (x + 1); i >= 1; i--) ans.push_back(i);

    reverse(all(ans));
    cout << ans.size() << endl;
    rep(i, 0, ans.size()) cout << ans[i] << " ";
}