Quotient Ranges(商列挙) (math/number-theory/quotient-ranges.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-24 02:34:04+09:00
• Include: #include "math/number-theory/quotient-ranges.hpp"

概要

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

使い方

• quotient_ranges(N): 戻り値の各要素を {{$x$,$y$},$z$} とする。$x \leq i \lt y$ を満たす整数の商($\lfloor \frac N i \rfloor$) が $z$ であることを意味する。$x$ の昇順で返す.

計算量

• $O(\sqrt N)$

Code

/**
 * @brief Quotient Ranges(商列挙)
 * 
 */
template< typename T >
vector< pair< pair< T, T >, T > > quotient_ranges(T N) {
  vector< pair< pair< T, T >, T > > ret;
  T l = 1;
  while(l <= N) {
    T q = N / l;
    T r = N / q + 1;
    ret.emplace_back(make_pair(l, r), q);
    l = r;
  }
  return ret;
}

#line 1 "math/number-theory/quotient-ranges.hpp"
/**
 * @brief Quotient Ranges(商列挙)
 * 
 */
template< typename T >
vector< pair< pair< T, T >, T > > quotient_ranges(T N) {
  vector< pair< pair< T, T >, T > > ret;
  T l = 1;
  while(l <= N) {
    T q = N / l;
    T r = N / q + 1;
    ret.emplace_back(make_pair(l, r), q);
    l = r;
  }
  return ret;
}

Back to top page