enumerate/floor_range.hpp

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

Required by

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

Verified with

• test/1_mytest/floor_ceil_ranges.test.cpp
• test/2_library_checker/number_theory/enumerate_quotients.test.cpp
• test/3_yukicoder/1260.test.cpp
• test/3_yukicoder/1276.test.cpp
• test/3_yukicoder/1573.test.cpp
• test/3_yukicoder/2266.test.cpp
• test/3_yukicoder/4954.test.cpp

Code

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

template <typename F>
void floor_range(u64 N, F f, bool Q_ASC = true, bool INCLUDE_Q_IS_0 = false) {
  u64 sq = sqrtl(N);
  u32 n = (sq * sq + sq <= N ? sq : sq - 1);
  if (Q_ASC) {
    if (INCLUDE_Q_IS_0) f(0, N + 1, infty<ll>);
    for (u32 q = 1; q <= n; ++q) { f(q, N / (q + 1) + 1, N / q + 1); }
    for (u32 l = sq; l >= 1; --l) { f(N / l, l, l + 1); }
  } else {
    for (u32 l = 1; l <= sq; ++l) { f(N / l, l, l + 1); }
    for (u32 q = n; q >= 1; --q) { f(q, N / (q + 1) + 1, N / q + 1); }
    if (INCLUDE_Q_IS_0) f(0, N + 1, infty<ll>);
  }
}

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

template <typename F>
void floor_range(u64 N, F f, bool Q_ASC = true, bool INCLUDE_Q_IS_0 = false) {
  u64 sq = sqrtl(N);
  u32 n = (sq * sq + sq <= N ? sq : sq - 1);
  if (Q_ASC) {
    if (INCLUDE_Q_IS_0) f(0, N + 1, infty<ll>);
    for (u32 q = 1; q <= n; ++q) { f(q, N / (q + 1) + 1, N / q + 1); }
    for (u32 l = sq; l >= 1; --l) { f(N / l, l, l + 1); }
  } else {
    for (u32 l = 1; l <= sq; ++l) { f(N / l, l, l + 1); }
    for (u32 q = n; q >= 1; --q) { f(q, N / (q + 1) + 1, N / q + 1); }
    if (INCLUDE_Q_IS_0) f(0, N + 1, infty<ll>);
  }
}

Back to top page