test/Quotient-Range.test.cpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00
• Problem: https://judge.yosupo.jp/problem/enumerate_quotients

Depends on

• Quotient-Range.cpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_quotients
#include "../Quotient-Range.cpp"
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long n;
    cin >> n;
    auto qr = quotient_range<long long>(n);
    assert(qr[0].first.first == 1);
    assert(qr.back().first.second == n);
    for (int i = 0; i < qr.size() - 1; i++) {
        assert(qr[i].first.second + 1 == qr[i + 1].first.first);
    }
    cout << qr.size() << endl;
    reverse(qr.begin(), qr.end());
    for (auto [rng, z] : qr) cout << z << " ";
    cout << endl;
}

#line 1 "test/Quotient-Range.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_quotients
#line 1 "Quotient-Range.cpp"
#include <bits/stdc++.h>
using namespace std;
template <class T>
vector<pair<pair<T, T>, T>> quotient_range(T n) {
    //[l,r]:quotient=z
    //[l,r]:increasing
    // z:decreasing
    // z=0 is not included
    T m = 1;
    vector<pair<pair<T, T>, T>> ret;
    while (m * m <= n) {
        ret.emplace_back(make_pair(m, m), n / m);
        m++;
    }
    for (T i = m; i >= 1; i--) {
        T L = n / (i + 1) + 1;
        T R = n / i;
        if (L <= R && ret.back().first.second < L) ret.emplace_back(make_pair(L, R), n / L);
    }
    return ret;
}
template <class T>
vector<pair<pair<T, T>, T>> quotient_range_ceil(T n) {
    const T inf = numeric_limits<T>::max();
    vector<pair<pair<T, T>, T>> res;
    if (n == 1) {
        res.push_back({{1, inf}, 1});
        return res;
    }
    T m = 1;
    while (m * m < n) {
        res.push_back({{m, m + 1}, (n + m - 1) / m});
        m++;
    }
    m = res.back().second - 1;
    while (m >= 1) {
        T l = (n + m - 1) / m;
        T r = m > 1 ? (n + m - 2) / (m - 1) : inf;
        if (l < r) res.push_back({{l, r}, m});
        m--;
    }
    return res;
}
#line 3 "test/Quotient-Range.test.cpp"
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long n;
    cin >> n;
    auto qr = quotient_range<long long>(n);
    assert(qr[0].first.first == 1);
    assert(qr.back().first.second == n);
    for (int i = 0; i < qr.size() - 1; i++) {
        assert(qr[i].first.second + 1 == qr[i + 1].first.first);
    }
    cout << qr.size() << endl;
    reverse(qr.begin(), qr.end());
    for (auto [rng, z] : qr) cout << z << " ";
    cout << endl;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_00	AC	130 ms	54 MB
g++	min_00	AC	5 ms	4 MB
g++	min_01	AC	4 ms	4 MB
g++	min_02	AC	4 ms	4 MB
g++	min_03	AC	4 ms	4 MB
g++	min_04	AC	4 ms	4 MB
g++	min_05	AC	4 ms	4 MB
g++	min_06	AC	4 ms	4 MB
g++	min_07	AC	4 ms	4 MB
g++	min_08	AC	4 ms	4 MB
g++	polynom_p1p1m1_00	AC	147 ms	53 MB
g++	polynom_p1p1m1_01	AC	72 ms	29 MB
g++	polynom_p1p1z_00	AC	150 ms	53 MB
g++	polynom_p1p1z_01	AC	71 ms	29 MB
g++	polynom_p1zm1_00	AC	150 ms	54 MB
g++	polynom_p1zm1_01	AC	73 ms	29 MB
g++	random_00	AC	65 ms	29 MB
g++	random_01	AC	102 ms	54 MB
g++	random_small_00	AC	5 ms	4 MB
g++	random_small_01	AC	4 ms	4 MB
g++	random_small_02	AC	4 ms	4 MB
g++	random_small_03	AC	4 ms	4 MB
g++	random_small_04	AC	4 ms	4 MB
g++	square_00	AC	54 ms	29 MB
g++	square_01	AC	66 ms	28 MB
clang++	example_00	AC	5 ms	4 MB
clang++	max_00	AC	126 ms	53 MB
clang++	min_00	AC	5 ms	4 MB
clang++	min_01	AC	4 ms	4 MB
clang++	min_02	AC	4 ms	4 MB
clang++	min_03	AC	4 ms	4 MB
clang++	min_04	AC	4 ms	4 MB
clang++	min_05	AC	4 ms	4 MB
clang++	min_06	AC	4 ms	4 MB
clang++	min_07	AC	4 ms	4 MB
clang++	min_08	AC	4 ms	4 MB
clang++	polynom_p1p1m1_00	AC	146 ms	53 MB
clang++	polynom_p1p1m1_01	AC	62 ms	29 MB
clang++	polynom_p1p1z_00	AC	129 ms	54 MB
clang++	polynom_p1p1z_01	AC	72 ms	28 MB
clang++	polynom_p1zm1_00	AC	149 ms	54 MB
clang++	polynom_p1zm1_01	AC	72 ms	29 MB
clang++	random_00	AC	67 ms	29 MB
clang++	random_01	AC	106 ms	53 MB
clang++	random_small_00	AC	5 ms	4 MB
clang++	random_small_01	AC	4 ms	4 MB
clang++	random_small_02	AC	4 ms	4 MB
clang++	random_small_03	AC	4 ms	4 MB
clang++	random_small_04	AC	4 ms	4 MB
clang++	square_00	AC	53 ms	28 MB
clang++	square_01	AC	66 ms	29 MB

Back to top page