(math/count_by_remainder.hpp)

View this file on GitHub
Last update: 2024-06-16 15:19:23+09:00
Include: #include "math/count_by_remainder.hpp"

$L$ 以上 $R$未満であって、$M$で割った余りが$b$である整数の個数を求める。こんなんソラで書くのは頭バグらせますからね。

count_by_remainder

T count_by_remainder(T l, T r, T b, T M)

計算量

$O(1)$

###　実装例

verify先がAtCしかみつからなかったので。

#include "math/count_by_remainder.hpp"

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  ll A,M,L,R; cin >> A >> M >> L >> R;
  A %= M;
  if (A < 0) A += M;  

  cout << count_by_remainder(L,R+1,A,M) << endl;
  return 0;
}

問題: [https://atcoder.jp/contests/abc334/submissions/54631702] ( https://atcoder.jp/contests/abc334/submissions/54631702 )

Code

#ifndef HARUILIB_MATH_COUNT_BY_REMAINDER_HPP
#define HARUILIB_MATH_COUNT_BY_REMAINDER_HPP

template <typename T= long long>
// l以上r未満で、Mで割った余りがbである整数の個数を求める
T count_by_remainder(T l, T r, T b, T M) {
  assert(l <= r && 0 <= b && b < M);
  r--;
  T k_min = (l - b + M - 1) / M;
  if (l - b + M - 1 < 0 && (l - b + M - 1) % M != 0) k_min--;

  T k_max = (r - b) / M;
  if (r - b < 0 && (r - b) % M != 0) k_max--;

  T ans = k_max - k_min + 1;
  //T mini = k_min * M + b;
  //T maxi = k_max * M + b;

  return ans;
}


#endif // HARUILIB_MATH_COUNT_BY_REMAINDER_HPP

#line 1 "math/count_by_remainder.hpp"



template <typename T= long long>
// l以上r未満で、Mで割った余りがbである整数の個数を求める
T count_by_remainder(T l, T r, T b, T M) {
  assert(l <= r && 0 <= b && b < M);
  r--;
  T k_min = (l - b + M - 1) / M;
  if (l - b + M - 1 < 0 && (l - b + M - 1) % M != 0) k_min--;

  T k_max = (r - b) / M;
  if (r - b < 0 && (r - b) % M != 0) k_max--;

  T ans = k_max - k_min + 1;
  //T mini = k_min * M + b;
  //T maxi = k_max * M + b;

  return ans;
}