Test/chinese_remainder.test.cpp

View this file on GitHub
Last update: 2021-06-05 13:56:14+09:00
Problem: https://yukicoder.me/problems/no/186

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/186"

#include "Mathematics/chinese_remainder.hpp"

#include <cstdio>
#include <utility>

int main() {
	using ll = long long;
	ll X[3], Y[3];
	for (int i = 0; i < 3; ++i) scanf("%lld %lld", X + i, Y + i);
	
	ll ans = 0, lcm = 1;
	for (int i = 0; i < 3; ++i) {
		auto [a, l] = tk::chinese_remainder(ans, lcm, X[i], Y[i]);
		if (l == 0) { puts("-1"); return 0; }
		ans = a; lcm = l;
	}
	
	printf("%lld\n", ans == 0 ? lcm : ans);
}

#line 1 "Test/chinese_remainder.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/186"

#line 1 "Mathematics/chinese_remainder.hpp"



#line 1 "Mathematics/euclid.hpp"



#include <cassert>
#include <utility>
#include <tuple>
#include <type_traits>
#include <cmath>

/**
 * @brief https://tkmst201.github.io/Library/Mathematics/euclid.hpp
 */
namespace tk {
template<typename T>
constexpr T gcd(T a, T b) noexcept {
	static_assert(std::is_integral<T>::value);
	assert(a >= 0);
	assert(b >= 0);
	while (b != 0) {
		const T t = a % b;
		a = b; b = t;
	}
	return a;
}

template<typename T>
constexpr T lcm(T a, T b) noexcept {
	static_assert(std::is_integral<T>::value);
	assert(a >= 0);
	assert(b >= 0);
	if (a == 0 || b == 0) return 0;
	return a / gcd(a, b) * b;
}

template<typename T>
constexpr std::tuple<T, T, T> ext_gcd(T a, T b) noexcept {
	static_assert(std::is_integral<T>::value);
	static_assert(std::is_signed<T>::value);
	assert(a != 0);
	assert(b != 0);
	T a1 = (a > 0) * 2 - 1, a2 = 0, b1 = 0, b2 = (b > 0) * 2 - 1;
	a = std::abs(a);
	b = std::abs(b);
	while (b > 0) {
		const T q = a / b;
		T tmp = a - q * b; a = b; b = tmp;
		tmp = a1 - q * b1; a1 = b1; b1 = tmp;
		tmp = a2 - q * b2; a2 = b2; b2 = tmp;
	}
	return {a, a1, a2};
}
} // namespace tk



#line 5 "Mathematics/chinese_remainder.hpp"

#line 9 "Mathematics/chinese_remainder.hpp"

/**
 * @brief https://tkmst201.github.io/Library/Mathematics/chinese_remainder.hpp
 */
namespace tk {
template<typename T>
constexpr std::pair<T, T> chinese_remainder(T b1, T m1, T b2, T m2) noexcept {
	static_assert(std::is_integral<T>::value);
	assert(m1 > 0);
	assert(m2 > 0);
	if (m1 < m2) { std::swap(b1, b2); std::swap(m1, m2); }
	b1 = b1 % m1 + (b1 >= 0 ? 0 : m1);
	b2 = b2 % m2 + (b2 >= 0 ? 0 : m2);
	auto [g, x, _] = ext_gcd(m1, m2);
	if ((b2 - b1) % g != 0) return {0, 0};
	const T pm2 = m2 / g;
	if (x < 0) x += pm2;
	const T t = ((b2 - b1) / g % pm2 + pm2) % pm2 * x % pm2;
	return {b1 + t * m1, m1 * pm2};
}
} // namespace tk



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

#include <cstdio>
#line 7 "Test/chinese_remainder.test.cpp"

int main() {
	using ll = long long;
	ll X[3], Y[3];
	for (int i = 0; i < 3; ++i) scanf("%lld %lld", X + i, Y + i);
	
	ll ans = 0, lcm = 1;
	for (int i = 0; i < 3; ++i) {
		auto [a, l] = tk::chinese_remainder(ans, lcm, X[i], Y[i]);
		if (l == 0) { puts("-1"); return 0; }
		ans = a; lcm = l;
	}
	
	printf("%lld\n", ans == 0 ? lcm : ans);
}