enumerate/floor_range.hpp

• View this file on GitHub
• Last update: 2023-11-24 15:08:08+09:00
• Include: #include "enumerate/floor_range.hpp"

Required by

• nt/mertens.hpp
• nt/range_rational_count.hpp

Verified with

• test/library_checker/math/enumerate_quotients.test.cpp
• test/mytest/floor_ceil_ranges.test.cpp
• test/yukicoder/1260.test.cpp
• test/yukicoder/1276.test.cpp
• test/yukicoder/1573.test.cpp
• test/yukicoder/2266.test.cpp
• test/yukicoder/4954.test.cpp

Code

// 商が q の区間 [l,r) を q について昇順

template <typename F>
void floor_range(u64 N, F f) {
  assert(N <= (u64(1) << 50));
  u64 sq = sqrtl(N);
  u32 n = (sq * sq + sq <= N ? sq : sq - 1);
  u64 prev = N + 1;
  for (u32 q = 1; q <= n; ++q) {
    u64 x = double(N) / (q + 1) + 1;
    f(q, x, prev), prev = x;
  }
  for (u32 l = sq; l >= 1; --l) { f(u64(double(N) / l), l, l + 1); }
}

#line 1 "enumerate/floor_range.hpp"
// 商が q の区間 [l,r) を q について昇順

template <typename F>
void floor_range(u64 N, F f) {
  assert(N <= (u64(1) << 50));
  u64 sq = sqrtl(N);
  u32 n = (sq * sq + sq <= N ? sq : sq - 1);
  u64 prev = N + 1;
  for (u32 q = 1; q <= n; ++q) {
    u64 x = double(N) / (q + 1) + 1;
    f(q, x, prev), prev = x;
  }
  for (u32 l = sq; l >= 1; --l) { f(u64(double(N) / l), l, l + 1); }
}

Back to top page