Enumerate Quotients (商列挙)
(lib/math/enumerate_quotients.hpp)

• View this file on GitHub
• Last update: 2024-05-04 18:06:16+09:00
• Include: #include "lib/math/enumerate_quotients.hpp"

Enumerate Quotients (商列挙)

概要

正整数 $N$ について、$1 \leq x \leq N$ における $\lfloor N / x \rfloor$ （商）としてあり得る値を列挙します。

また、その商となる $x$ の区間も同時に取得します。

計算量

• $\mathrm{O}(\sqrt{N})$

Verified with

• test/library_checker/number_theory/enumerate_quotients.test.cpp

Code

#pragma once

/**
 * @brief Enumerate Quotients (商列挙)
 * @docs docs/math/enumerate_quotients.md
 */

template <typename T>
vector<tuple<T, T, T>> enumerate_quotients(const T &n){
    vector<tuple<T, T, T>> res;
    for(T l = 1; l <= n;){
        const T quotient = n / l;
        const T r = n / quotient + 1;

        // [l, r)
        res.emplace_back(l, r, quotient);
        l = r;
    }
    return res;
}

#line 2 "lib/math/enumerate_quotients.hpp"

/**
 * @brief Enumerate Quotients (商列挙)
 * @docs docs/math/enumerate_quotients.md
 */

template <typename T>
vector<tuple<T, T, T>> enumerate_quotients(const T &n){
    vector<tuple<T, T, T>> res;
    for(T l = 1; l <= n;){
        const T quotient = n / l;
        const T r = n / quotient + 1;

        // [l, r)
        res.emplace_back(l, r, quotient);
        l = r;
    }
    return res;
}

Back to top page