mod/range_freq_mod.hpp

View this file on GitHub
Last update: 2026-08-15 15:50:39+09:00
Include: #include "mod/range_freq_mod.hpp"

Code

// count x in [L,R) such that (x mod mod) in [lo,hi)
template <typename I>
I range_freq_mod(I L, I R, I lo, I hi, I mod) {
  assert(0 <= lo && lo <= hi && hi <= mod);
  auto f = [&](I x) -> I {
    auto [q, r] = divmod<I>(x, mod);
    I a = max<I>(lo, 0), b = min<I>(hi, r);
    return q * (hi - lo) + max<I>(b - a, 0);
  };
  return f(R) - f(L);
}

#line 1 "mod/range_freq_mod.hpp"
// count x in [L,R) such that (x mod mod) in [lo,hi)
template <typename I>
I range_freq_mod(I L, I R, I lo, I hi, I mod) {
  assert(0 <= lo && lo <= hi && hi <= mod);
  auto f = [&](I x) -> I {
    auto [q, r] = divmod<I>(x, mod);
    I a = max<I>(lo, 0), b = min<I>(hi, r);
    return q * (hi - lo) + max<I>(b - a, 0);
  };
  return f(R) - f(L);
}