C++ Library for Competitive Programming
/*
* @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;
}