Enumerate Quotients (商列挙) (math/number-theory/enumerate-quotients.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-05-26 19:28:30+09:00
• Include: #include "math/number-theory/enumerate-quotients.hpp"

整数 $n$ が与えられたとき, $n$ の商 ($\lfloor \frac n i \rfloor$) ($1 \leq i \leq n$) の値と対応する区間を列挙します。

enumerate_quotients

template <typename T>
vector< tuple< T, T, T > > enumerate_quotients(T n)

戻り値の各要素を $\{q, l, r\}$ としたとき、$l \leq i \lt r$ を満たす整数 $i$ の商($\lfloor \frac n i \rfloor$) が $q$ であることを意味します。$q$ の昇順で返します。

制約

• $1 \leq n$

計算量

• $O(\sqrt n)$

Verified with

• test/verify/yosupo-enumerate-quotients.test.cpp

Code

template <typename T>
vector<tuple<T, T, T> > enumerate_quotients(T n) {
  T l = 1;
  vector<tuple<T, T, T> > quotients;
  while (l <= n) {
    T q = n / l;
    T r = n / q + 1;
    quotients.emplace_back(q, l, r);
    l = r;
  }
  reverse(quotients.begin(), quotients.end());
  return quotients;
}

#line 1 "math/number-theory/enumerate-quotients.hpp"
template <typename T>
vector<tuple<T, T, T> > enumerate_quotients(T n) {
  T l = 1;
  vector<tuple<T, T, T> > quotients;
  while (l <= n) {
    T q = n / l;
    T r = n / q + 1;
    quotients.emplace_back(q, l, r);
    l = r;
  }
  reverse(quotients.begin(), quotients.end());
  return quotients;
}

Back to top page