This documentation is automatically generated by online-judge-tools/verification-helper
#include "math/count_by_remainder.hpp"
$L$ 以上 $R$未満であって、$M$で割った余りが$b$である整数の個数を求める。 こんなんソラで書くのは頭バグらせますからね。
T count_by_remainder(T l, T r, T b, T M)
### 実装例
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 )
#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;
}