math/enumerate_quotients.hpp

• View this file on GitHub
• Last update: 2025-04-05 12:46:42+09:00
• Include: #include "math/enumerate_quotients.hpp"

Depends on

• math/frac_floor.hpp
• math/sqrt_floor.hpp

Required by

• math/multiplicative_function/counting_square_free.hpp
• math/multiplicative_function/prefix_sum.hpp
• math/multiplicative_function/prime_counting.hpp

Verified with

• verify/unit_test/isprime_table_extend.test.cpp
• verify/unit_test/lpf_table_extend.test.cpp
• verify/unit_test/prime_table_extend.test.cpp
• verify/yosupo_math/enumerate_quotients.test.cpp
• verify/yosupo_math/prefix_sum_of_multiplicative_function.test.cpp
• verify/yosupo_math/prime_counting.test.cpp

Code

#ifndef KK2_MATH_ENUMERATE_QUOTIENTS_HPP
#define KK2_MATH_ENUMERATE_QUOTIENTS_HPP 1

#include <numeric>
#include <vector>

#include "sqrt_floor.hpp"

namespace kk2 {

template <class T> struct EnumerateQuotients {
    T n;
    int sqrt_n;
    std::vector<T> res;

    EnumerateQuotients(T n) : n(n), sqrt_n(sqrt_floor(n)) {
        res.resize(sqrt_n + n / (sqrt_n + 1));
        std::iota(res.begin(), res.begin() + sqrt_n, 1);
        for (T i = n / (sqrt_n + 1), j = sqrt_n; i; --i, ++j) res[j] = n / i;
    }

    const std::vector<T> &get() const { return res; }

    int size() const { return res.size(); }

    const T &operator[](int i) const { return res[i]; }

    int idx(T x) const {
        if (x <= sqrt_n) return x - 1;
        return size() - n / x;
    }
};

} // namespace kk2

#endif // KK2_MATH_ENUMERATE_QUOTIENTS_HPP

#line 1 "math/enumerate_quotients.hpp"



#include <numeric>
#include <vector>

#line 1 "math/sqrt_floor.hpp"



#include <cmath>

#line 1 "math/frac_floor.hpp"



#include <cassert>

namespace kk2 {

// floor(x) = ceil(x) - 1 (for all x not in Z) ...(1)
// floor(x) = -ceil(-x)   (for all x)          ...(2)

// return floor(a / b)
template <typename T, typename U> constexpr T fracfloor(T a, U b) {
    assert(b != 0);
    if (a % b == 0) return a / b;
    if (a >= 0) return a / b;

    // floor(x) = -ceil(-x)      by (2)
    //          = -floor(-x) - 1 by (1)
    return -((-a) / b) - 1;
}

// return ceil(a / b)
template <typename T, typename U> constexpr T fracceil(T a, U b) {
    assert(b != 0);
    if (a % b == 0) return a / b;
    if (a >= 0) return a / b + 1;

    // ceil(x) = -floor(-x)      by (2)
    return -((-a) / b);
}

} // namespace kk2


#line 7 "math/sqrt_floor.hpp"

namespace kk2 {

template <typename T> T sqrt_floor(T n) {
    assert(n >= 0);
    if (n == T(0)) return 0;
    T x = std::sqrt(n);
    if (x == T(0)) ++x;
    while (x > kk2::fracfloor(n, x)) --x;
    while (x + 1 <= kk2::fracfloor(n, x + 1)) ++x;
    return x;
}

template <typename T> T sqrt_ceil(T n) {
    assert(n >= 0);
    if (n <= T(1)) return n;
    T x = std::sqrt(n);
    if (x == T(0)) ++x;
    while (x < kk2::fracceil(n, x)) ++x;
    while (x - 1 >= kk2::fracceil(n, x - 1)) --x;
    return x;
}

} // namespace kk2


#line 8 "math/enumerate_quotients.hpp"

namespace kk2 {

template <class T> struct EnumerateQuotients {
    T n;
    int sqrt_n;
    std::vector<T> res;

    EnumerateQuotients(T n) : n(n), sqrt_n(sqrt_floor(n)) {
        res.resize(sqrt_n + n / (sqrt_n + 1));
        std::iota(res.begin(), res.begin() + sqrt_n, 1);
        for (T i = n / (sqrt_n + 1), j = sqrt_n; i; --i, ++j) res[j] = n / i;
    }

    const std::vector<T> &get() const { return res; }

    int size() const { return res.size(); }

    const T &operator[](int i) const { return res[i]; }

    int idx(T x) const {
        if (x <= sqrt_n) return x - 1;
        return size() - n / x;
    }
};

} // namespace kk2

Back to top page