This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub maspypy/library

#include "mod/range_freq_of_linear.hpp"

#include "mod/floor_sum_of_linear.hpp" // sum_{x in [L,R)} floor(ax + b, mod) // I は範囲内で ax+b がオーバーフローしない程度 template <typename O = i128, typename I = long long> I range_freq_of_linear(I L, I R, I a, I b, I mod, I lo, I hi) { if (lo >= hi) return 0; assert(0 <= lo && lo < hi && hi <= mod); O x1 = floor_sum_of_linear<O, I>(L, R, a, b - lo, mod); O x2 = floor_sum_of_linear<O, I>(L, R, a, b - hi, mod); return x1 - x2; }

#line 2 "mod/floor_sum_of_linear.hpp" // sum_{x in [L,R)} floor(ax + b, mod) // I は範囲内で ax+b がオーバーフローしない程度 template <typename O = i128, typename I = long long> O floor_sum_of_linear(I L, I R, I a, I b, I mod) { assert(L <= R); O res = 0; b += L * a; I N = R - L; if (b < 0) { I k = ceil(-b, mod); b += k * mod; res -= O(N) * O(k); } while (N) { I q; tie(q, a) = divmod(a, mod); res += (N & 1 ? O(N) * O((N - 1) / 2) * O(q) : O(N / 2) * O(N - 1) * O(q)); if (b >= mod) { tie(q, b) = divmod(b, mod); res += O(N) * q; } tie(N, b) = divmod(a * N + b, mod); tie(a, mod) = mp(mod, a); } return res; } #line 2 "mod/range_freq_of_linear.hpp" // sum_{x in [L,R)} floor(ax + b, mod) // I は範囲内で ax+b がオーバーフローしない程度 template <typename O = i128, typename I = long long> I range_freq_of_linear(I L, I R, I a, I b, I mod, I lo, I hi) { if (lo >= hi) return 0; assert(0 <= lo && lo < hi && hi <= mod); O x1 = floor_sum_of_linear<O, I>(L, R, a, b - lo, mod); O x2 = floor_sum_of_linear<O, I>(L, R, a, b - hi, mod); return x1 - x2; }