C++ Library for Competitive Programming
/*
* @title 数学/sum of floor of linear
*
* verification-helper: PROBLEM https://judge.yosupo.jp/problem/sum_of_floor_of_linear
*/
#include <iostream>
#include "emthrm/math/floor_sum.hpp"
int main() {
int t;
std::cin >> t;
while (t--) {
int n, m, a, b;
std::cin >> n >> m >> a >> b;
std::cout << emthrm::floor_sum(a, b, m, n) << '\n';
}
return 0;
}
#line 1 "test/math/floor_sum.test.cpp"
/*
* @title 数学/sum of floor of linear
*
* verification-helper: PROBLEM https://judge.yosupo.jp/problem/sum_of_floor_of_linear
*/
#include <iostream>
#line 1 "include/emthrm/math/floor_sum.hpp"
#include <utility>
namespace emthrm {
long long floor_sum(long long a, long long b, long long m, long long n) {
long long res = 0;
if (a < 0) {
long long nxt_a = a % m;
if (nxt_a < 0) nxt_a += m;
res -= n * (n - 1) / 2 * ((nxt_a - a) / m);
a = nxt_a;
}
if (b < 0) {
long long nxt_b = b % m;
if (nxt_b < 0) nxt_b += m;
res -= n * ((nxt_b - b) / m);
b = nxt_b;
}
while (true) {
if (a >= m) {
res += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
res += n * (b / m);
b %= m;
}
const long long y_max = a * n + b;
if (y_max < m) break;
b = y_max % m;
n = y_max / m;
std::swap(a, m);
}
return res;
}
} // namespace emthrm
#line 10 "test/math/floor_sum.test.cpp"
int main() {
int t;
std::cin >> t;
while (t--) {
int n, m, a, b;
std::cin >> n >> m >> a >> b;
std::cout << emthrm::floor_sum(a, b, m, n) << '\n';
}
return 0;
}