This documentation is automatically generated by online-judge-tools/verification-helper
#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$ の昇順で返す./**
* @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;
}