Enumerate the range of $\left\lfloor \frac{A}{x} \right\rfloor$ (tools/floor_quotients.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2023-07-09 15:30:52+09:00
Include: #include "tools/floor_quotients.hpp"

template <typename T>
std::vector<std::tuple<T, T, T>> floor_quotients(T A);

It returns the tuples such that the $i$-th tuple $(l_i, r_i, q_i)$ satisfies $l_i \leq x < r_i \Rightarrow \left\lfloor \frac{A}{x} \right\rfloor = q_i$, in ascending order of $l_i$. The last tuple would be $(A + 1, \infty, 0)$ mathematically, but it actually returns std::numeric_limits<T>::max() instead of $\infty$ since a integral type <T> cannot represent infinity.

Constraints

<T> is a built-in integral type.
$A \geq 0$

Time Complexity

$O(\sqrt{A})$

License

Author

anqooqie

Verified with

tests/floor_quotients.test.cpp

Code

#ifndef TOOLS_FLOOR_QUOTIENTS_HPP
#define TOOLS_FLOOR_QUOTIENTS_HPP

#include <vector>
#include <tuple>
#include <cassert>
#include <limits>

namespace tools {
  template <typename T>
  ::std::vector<::std::tuple<T, T, T>> floor_quotients(const T A) {
    assert(A >= 0);

    ::std::vector<::std::tuple<T, T, T>> res;
    T x;
    for (x = 1; x * x <= A; ++x) {
      res.emplace_back(x, x + 1, A / x);
    }
    for (T q = A / x; q > 0; --q) {
      res.emplace_back(A / (q + 1) + 1, A / q + 1, q);
    }
    res.emplace_back(A + 1, ::std::numeric_limits<T>::max(), 0);

    return res;
  }
}

#endif

#line 1 "tools/floor_quotients.hpp"



#include <vector>
#include <tuple>
#include <cassert>
#include <limits>

namespace tools {
  template <typename T>
  ::std::vector<::std::tuple<T, T, T>> floor_quotients(const T A) {
    assert(A >= 0);

    ::std::vector<::std::tuple<T, T, T>> res;
    T x;
    for (x = 1; x * x <= A; ++x) {
      res.emplace_back(x, x + 1, A / x);
    }
    for (T q = A / x; q > 0; --q) {
      res.emplace_back(A / (q + 1) + 1, A / q + 1, q);
    }
    res.emplace_back(A + 1, ::std::numeric_limits<T>::max(), 0);

    return res;
  }
}