Enumerate the range of $\left\lceil \frac{A}{x} \right\rceil$ (tools/ceil_quotients.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2025-02-10 01:30:13+09:00
Include: #include "tools/ceil_quotients.hpp"

template <typename T>
std::vector<std::tuple<T, T, T>> ceil_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\lceil \frac{A}{x} \right\rceil = q_i$, in ascending order of $l_i$. The last tuple would be

\[\begin{align*} \left\{\begin{array}{ll} (A, \infty, 1) & \text{(if $A > 0$)}\\ (1, \infty, 0) & \text{(if $A = 0$)} \end{array}\right.& \end{align*}\]

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

Depends on

Verified with

tests/ceil_quotients.test.cpp

Code

#ifndef TOOLS_CEIL_QUOTIENTS_HPP
#define TOOLS_CEIL_QUOTIENTS_HPP

#include <vector>
#include <tuple>
#include <cassert>
#include <limits>
#include "tools/ceil.hpp"

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

    ::std::vector<::std::tuple<T, T, T>> res;
    if (A == 0) {
      res.emplace_back(1, ::std::numeric_limits<T>::max(), 0);
      return res;
    }

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

    return res;
  }
}

#endif

#line 1 "tools/ceil_quotients.hpp"



#include <vector>
#include <tuple>
#include <cassert>
#include <limits>
#line 1 "tools/ceil.hpp"



#line 5 "tools/ceil.hpp"
#include <type_traits>
#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_unsigned.hpp"



#line 5 "tools/is_unsigned.hpp"

namespace tools {
  template <typename T>
  struct is_unsigned : ::std::is_unsigned<T> {};

  template <typename T>
  inline constexpr bool is_unsigned_v = ::tools::is_unsigned<T>::value;
}


#line 8 "tools/ceil.hpp"

namespace tools {
  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> ceil(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x > 0) {
        return (x - 1) / y + 1;
      } else {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      }
    } else {
      if (x >= 0) {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      } else {
        return (x + 1) / y + 1;
      }
    }
  }
}


#line 9 "tools/ceil_quotients.hpp"

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

    ::std::vector<::std::tuple<T, T, T>> res;
    if (A == 0) {
      res.emplace_back(1, ::std::numeric_limits<T>::max(), 0);
      return res;
    }

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

    return res;
  }
}