enumerate/ceil_range.hpp

View this file on GitHub
Last update: 2023-02-17 11:47:17+09:00
Include: #include "enumerate/ceil_range.hpp"

Verified with

test/mytest/floor_ceil_ranges.test.cpp

Code

// 商が q の区間 [l,r) を q について昇順
template <typename F>
void ceil_range(ll N, F f) {
  assert(N <= (1LL << 50));
  ll sq = sqrtl(N);
  ll prev = infty<ll>;
  for (int q = 1; q <= sq; ++q) {
    ll x = double(N + q - 1) / q;
    f(q, x, prev), prev = x;
  }
  int n = (N <= sq * sq + sq ? sq : sq + 1);
  if (N == sq * sq) --n;
  for (int l = n; l >= 1; --l) { f(double(N + l - 1) / l, l, l + 1); }
}

#line 1 "enumerate/ceil_range.hpp"
// 商が q の区間 [l,r) を q について昇順
template <typename F>
void ceil_range(ll N, F f) {
  assert(N <= (1LL << 50));
  ll sq = sqrtl(N);
  ll prev = infty<ll>;
  for (int q = 1; q <= sq; ++q) {
    ll x = double(N + q - 1) / q;
    f(q, x, prev), prev = x;
  }
  int n = (N <= sq * sq + sq ? sq : sq + 1);
  if (N == sq * sq) --n;
  for (int l = n; l >= 1; --l) { f(double(N + l - 1) / l, l, l + 1); }
}