Intervals with Equal Quotients
(math/number-theory/quotients.hpp)

• View this file on GitHub
• Last update: 2024-01-08 17:31:43+09:00
• Include: #include "math/number-theory/quotients.hpp"

Verified with

• test/yosupo/enumerate_quotients.test.cpp

Code

#pragma once
#include <vector>

/**
 * @brief Intervals with Equal Quotients
 */
template <typename T>
std::vector<std::pair<T, T>> quotient_ranges(T n) {
    std::vector<std::pair<T, T>> ret;
    T i = 1;
    while (i <= n) {
        T q = n / i;
        T j = n / q + 1;
        ret.emplace_back(i, j);
        i = j;
    }
    return ret;
}

#line 2 "math/number-theory/quotients.hpp"
#include <vector>

/**
 * @brief Intervals with Equal Quotients
 */
template <typename T>
std::vector<std::pair<T, T>> quotient_ranges(T n) {
    std::vector<std::pair<T, T>> ret;
    T i = 1;
    while (i <= n) {
        T q = n / i;
        T j = n / q + 1;
        ret.emplace_back(i, j);
        i = j;
    }
    return ret;
}

Back to top page