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/simultaneous_linear_congruence.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::simultaneous_linear_congruence( std::vector<long long>(N, 1), x, y); if (mod == 0) { std::cout << "-1\n"; } else { std::cout << (ans == 0 ? mod : ans) << '\n'; } return 0; }
#line 1 "test/math/simultaneous_linear_congruence.test.cpp" /* * @title 数学/連立線形合同式 * * verification-helper: PROBLEM https://yukicoder.me/problems/no/186 */ #include <iostream> #include <vector> #line 1 "include/emthrm/math/simultaneous_linear_congruence.hpp" #include <numeric> #include <utility> #line 7 "include/emthrm/math/simultaneous_linear_congruence.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/simultaneous_linear_congruence.hpp" namespace emthrm { template <typename T> std::pair<T, T> simultaneous_linear_congruence(const std::vector<T>& a, const std::vector<T>& b, const std::vector<T>& m) { const int n = a.size(); T x = 0, md = 1; for (int i = 0; i < n; ++i) { const T p = md * a[i], q = -x * a[i] + b[i], g = std::gcd(p, m[i]); if (q % g != 0) return {0, -1}; const T m_i = m[i] / g; x += md * (q / g * mod_inv(p / g, m_i) % m_i); md *= m_i; } return {x < 0 ? x + md : x, md}; } } // namespace emthrm #line 11 "test/math/simultaneous_linear_congruence.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::simultaneous_linear_congruence( std::vector<long long>(N, 1), x, y); if (mod == 0) { std::cout << "-1\n"; } else { std::cout << (ans == 0 ? mod : ans) << '\n'; } return 0; }