C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title 数学/中国剰余定理 * * verification-helper: PROBLEM https://yukicoder.me/problems/no/186 */ #include <iostream> #include <vector> #include "emthrm/math/chinese_remainder_theorem.hpp" int main() { constexpr int N = 3; std::vector<long long> x(N), y(N); for (int i = 0; i < N; ++i) { std::cin >> x[i] >> y[i]; } const auto [ans, mod] = emthrm::chinese_remainder_theorem(x, y); if (mod == 0) { std::cout << "-1\n"; } else { std::cout << (ans == 0 ? mod : ans) << '\n'; } return 0; }
#line 1 "test/math/chinese_remainder_theorem.test.cpp" /* * @title 数学/中国剰余定理 * * verification-helper: PROBLEM https://yukicoder.me/problems/no/186 */ #include <iostream> #include <vector> #line 1 "include/emthrm/math/chinese_remainder_theorem.hpp" #include <numeric> #include <utility> #line 7 "include/emthrm/math/chinese_remainder_theorem.hpp" #line 1 "include/emthrm/math/mod_inv.hpp" #line 6 "include/emthrm/math/mod_inv.hpp" namespace emthrm { long long mod_inv(long long a, const int m) { if ((a %= m) < 0) a += m; if (std::gcd(a, m) != 1) return -1; long long x = 1; for (long long b = m, u = 0; b > 0;) { const long long q = a / b; std::swap(a -= q * b, b); std::swap(x -= q * u, u); } x %= m; return x < 0 ? x + m : x; } } // namespace emthrm #line 9 "include/emthrm/math/chinese_remainder_theorem.hpp" namespace emthrm { template <typename T> std::pair<T, T> chinese_remainder_theorem(std::vector<T> b, std::vector<T> m) { const int n = b.size(); T x = 0, md = 1; for (int i = 0; i < n; ++i) { if ((b[i] %= m[i]) < 0) b[i] += m[i]; if (md < m[i]) { std::swap(x, b[i]); std::swap(md, m[i]); } if (md % m[i] == 0) { if (x % m[i] != b[i]) return {0, 0}; continue; } const T g = std::gcd(md, m[i]); if ((b[i] - x) % g != 0) return {0, 0}; const T u_i = m[i] / g; x += (b[i] - x) / g % u_i * mod_inv(md / g, u_i) % u_i * md; md *= u_i; if (x < 0) x += md; } return {x, md}; } } // namespace emthrm #line 11 "test/math/chinese_remainder_theorem.test.cpp" int main() { constexpr int N = 3; std::vector<long long> x(N), y(N); for (int i = 0; i < N; ++i) { std::cin >> x[i] >> y[i]; } const auto [ans, mod] = emthrm::chinese_remainder_theorem(x, y); if (mod == 0) { std::cout << "-1\n"; } else { std::cout << (ans == 0 ? mod : ans) << '\n'; } return 0; }