enumerate/ceil_range.hpp

• View this file on GitHub
• Last update: 2024-09-14 09:20:23+09:00
• Include: #include "enumerate/ceil_range.hpp"

Verified with

• test/1_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 = (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((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 = (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((N + l - 1) / l, l, l + 1); }
}

Back to top page