test/prefix_min_of_mod_of_linear.test.cpp

test/prefix_min_of_mod_of_linear.test.cpp · GitHub で見る

依存ライブラリ

コード

#define PROBLEM "https://judge.yosupo.jp/problem/min_of_mod_of_linear"
#include "../math/prefix_min_of_mod_of_linear.hpp"
#include <cstdint>
#include <iostream>

int main() {
	std::cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	std::cin >> t;
	while (t--) {
		std::uint64_t n, m, a, b, answer = 0;
		std::cin >> n >> m >> a >> b;
		prefix_min_of_mod_of_linear(n, m, a, b, [&](ModLinearPrefixMinSegment part) {
			answer = part.y - part.dy * (part.count - 1);
		});
		std::cout << answer << '\n';
	}
}

#line 1 "test/prefix_min_of_mod_of_linear.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/min_of_mod_of_linear"
#line 1 "math/prefix_min_of_mod_of_linear.hpp"



#include <cassert>
#include <cstdint>
#include <limits>
#include <vector>
#line 1 "components/mod_linear_prefix_min.hpp"



#line 5 "components/mod_linear_prefix_min.hpp"
#include <type_traits>

namespace mod_linear_detail {
template <class U, class Emit>
void prefix_min(U n, U m, U a, U b, Emit &&emit) {
	using W = std::conditional_t<(sizeof(U) <= 4), std::uint64_t, __uint128_t>;
	bool first = true;
	if (a && b && n > 1) {
		U p = m - a, q = a, sp = 1, sq = 1, x = 0, remaining = n - 1;
		for (;;) {
			if (p <= b) {
				U k = b / p;
				bool final = W(k) * sp > remaining;
				if (final) k = remaining / sp;
				if (k) {
					if (first) emit(U(0), b, sp, p, U(k + 1));
					else emit(U(x + sp), U(b - p), sp, p, k);
					first = false;
					x += k * sp;
					b -= k * p;
					remaining -= k * sp;
				}
				if (final || !b) break;
			}
			if (sp > remaining || sq > remaining - sp) break;
			if (p > q) {
				U k = (p - b - 1) / q + 1, d = k * q;
				if (d == p) break;
				if (d > p) --k;
				sp += k * sq;
				if (sp > remaining) break;
				p -= k * q;
			} else {
				U k = q / p;
				q %= p;
				if (!q) break;
				sq += k * sp;
			}
		}
	}
	if (first) emit(U(0), b, U(0), U(0), U(1));
}
}


#line 9 "math/prefix_min_of_mod_of_linear.hpp"

struct ModLinearPrefixMinSegment {
	std::uint64_t x, y, dx, dy, count;
	bool operator==(const ModLinearPrefixMinSegment &) const = default;
};

template <class Emit>
void prefix_min_of_mod_of_linear(std::uint64_t n, std::uint64_t m, std::uint64_t a, std::uint64_t b, Emit &&emit) {
	assert(m > 0);
	if (!n) return;
	if (a >= m) a %= m;
	if (b >= m) b %= m;
	if (n > m) n = m;
	auto output = [&](auto x, auto y, auto dx, auto dy, auto count) {
		emit(ModLinearPrefixMinSegment{x, y, dx, dy, count});
	};
	if (m <= std::numeric_limits<std::uint32_t>::max())
		mod_linear_detail::prefix_min<std::uint32_t>(n, m, a, b, output);
	else mod_linear_detail::prefix_min(n, m, a, b, output);
}

inline std::vector<ModLinearPrefixMinSegment> prefix_min_of_mod_of_linear(std::uint64_t n, std::uint64_t m,
		std::uint64_t a, std::uint64_t b) {
	std::vector<ModLinearPrefixMinSegment> result;
	prefix_min_of_mod_of_linear(n, m, a, b, [&](ModLinearPrefixMinSegment part) { result.push_back(part); });
	return result;
}


#line 4 "test/prefix_min_of_mod_of_linear.test.cpp"
#include <iostream>

int main() {
	std::cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	std::cin >> t;
	while (t--) {
		std::uint64_t n, m, a, b, answer = 0;
		std::cin >> n >> m >> a >> b;
		prefix_min_of_mod_of_linear(n, m, a, b, [&](ModLinearPrefixMinSegment part) {
			answer = part.y - part.dy * (part.count - 1);
		});
		std::cout << answer << '\n';
	}
}