Luzhiled's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ei1333/library

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

概要

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

使い方

計算量

Code

/**
 * @brief Quotient Ranges(商列挙)
 * @docs docs/quotient-ranges.md
 */
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(商列挙)
 * @docs docs/quotient-ranges.md
 */
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