This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#define PROBLEM "https://judge.yosupo.jp/problem/sum_of_floor_of_linear" #include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; #include "math/floor_sum.hpp" signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); int tc; cin >> tc; while(tc--){ int n, m, a, b; cin >> n >> m >> a >> b; cout << sum_of_floor<ll>(n, m, a, b) << '\n'; } }
#line 1 "math/test/Sum_of_Floor_of_Linear.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/sum_of_floor_of_linear" #include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; #line 2 "math/floor_sum.hpp" // sum_{0 <= i < N} (ai + b) // m template <typename T> T sum_of_floor(T n, T m, T a, T b) { T ret = 0; if (a >= m) ret += (n - 1) * n * (a / m) / 2, a %= m; if (b >= m) ret += n * (b / m), b %= m; T y = (a * n + b) / m; if (y == 0) return ret; T x = y * m - b; ret += (n - (x + a - 1) / a) * y; ret += sum_of_floor(y, a, m, (a - x % a) % a); return ret; } // verify www.codechef.com/viewsolution/36222026 // count x : ax + b mod m < yr, 0 <= x < xr template <typename T> T mod_affine_range_counting(T a, T b, T m, T xr, T yr) { assert(0 <= yr && yr <= m); return sum_of_floor(xr, m, a, b + m) - sum_of_floor(xr, m, a, b + m - yr); } #line 11 "math/test/Sum_of_Floor_of_Linear.test.cpp" signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); int tc; cin >> tc; while(tc--){ int n, m, a, b; cin >> n >> m >> a >> b; cout << sum_of_floor<ll>(n, m, a, b) << '\n'; } }