This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub tkmst201/Library
#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); }