Test/sum_of_floor_of_linear.test.cpp

• View this file on GitHub
• Last update: 2021-04-13 10:29:45+09:00
• Problem: https://judge.yosupo.jp/problem/sum_of_floor_of_linear

Depends on

• Sum of Floor of Linear (Mathematics/sum_of_floor_of_linear.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/sum_of_floor_of_linear"

#include "Mathematics/sum_of_floor_of_linear.hpp"

#include <cstdio>

int main() {
	int T;
	scanf("%d", &T);
	using ll = long long;
	while (T--) {
		int n, m, a, b;
		scanf("%d %d %d %d", &n, &m, &a, &b);
		printf("%lld\n", tk::sum_of_floor_of_linear<ll>(n, m, a, b));
	}
}

#line 1 "Test/sum_of_floor_of_linear.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/sum_of_floor_of_linear"

#line 1 "Mathematics/sum_of_floor_of_linear.hpp"



#include <utility>
#include <cassert>
#include <type_traits>

/**
 * @brief https://tkmst201.github.io/Library/Mathematics/sum_of_floor_of_linear.hpp
 */
namespace tk {
template<typename T>
T sum_of_floor_of_linear(T n, T m, T a, T b) {
	static_assert(std::is_integral<T>::value);
	assert(n >= 0);
	assert(m > 0);
	assert(a >= 0);
	assert(b >= 0);
	if (n == 0) return 0;
	const T qa = a / m, qb = b / m;
	T res = n * (n - 1) / 2 * qa + n * qb;
	a -= qa * m;
	b -= qb * m;
	if (a == 0) return res;
	const T q = (a * n + b) / m, r = (a * n + b) - q * m;
	return res + sum_of_floor_of_linear(q, a, m, r);
}
} // namespace tk



#line 4 "Test/sum_of_floor_of_linear.test.cpp"

#include <cstdio>

int main() {
	int T;
	scanf("%d", &T);
	using ll = long long;
	while (T--) {
		int n, m, a, b;
		scanf("%d %d %d %d", &n, &m, &a, &b);
		printf("%lld\n", tk::sum_of_floor_of_linear<ll>(n, m, a, b));
	}
}

Back to top page