#line 1 "test/math/yuki_447.test.cpp" #define PROBLEM "https://yukicoder.me/problems/447" #line 2 "template/template.hpp" #include #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) #define all(v) v.begin(), v.end() using ll = long long; using ld = long double; using ull = unsigned long long; template bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } namespace lib { using namespace std; } // namespace lib // using namespace lib; #line 2 "math/crt.hpp" #line 2 "math/ext_gcd.hpp" #line 4 "math/ext_gcd.hpp" // https://github.com/maspypy/library/blob/main/nt/extgcd.hpp namespace lib { tuple Farey_lr(ll a, ll b) { assert(a > 0 && b > 0); /* Farey 数列で、a/b が最初に現れるときの、左右を求める。 a/b = 19/12 → (x1/y1, x2/y2) = (11/7, 8/5) → (11,7,8,5) を返す。 */ if (a == b) return {0, 1, 1, 0}; ll q = (a - 1) / b; auto [x1, y1, x2, y2] = Farey_lr(b, a - q * b); return {q * x2 + y2, x2, q * x1 + y1, x1}; } tuple extgcd(ll a, ll b) { // ax + by = d の最小解 (x, y, d) を返す。 // (|x|+|y|, x) に関する辞書順最小とする。 auto [x1, y1, x2, y2] = Farey_lr(a, b); tie(x1, y1) = make_pair(y1, -x1); tie(x2, y2) = make_pair(-y2, x2); ll g = a * x1 + b * y1; pair key1 = make_pair(abs(x1) + abs(y1), x1); pair key2 = make_pair(abs(x2) + abs(y2), x2); return (key1 < key2 ? make_tuple(x1, y1, g) : make_tuple(x2, y2, g)); } } // namespace lib #line 5 "math/crt.hpp" namespace lib { std::pair crt(const std::vector &b, const std::vector &m) { ll r = 0, mod = 1; rep(i, 0, int(b.size())) { auto [p, q, d] = extgcd(mod, m[i]); if ((b[i] - r) % d != 0) return {0, -1}; ll x = (b[i] - r) / d * p % (m[i] / d); r += x * mod; mod *= m[i] / d; } return {r, mod}; } } // namespace lib #line 5 "test/math/yuki_447.test.cpp" int main() { std::vector x(3), y(3); rep(i,0,3) { std::cin >> x[i] >> y[i]; } auto [r, m] = lib::crt(x, y); if(m < 0) { std::cout << -1 << '\n'; } else { if(r == 0) r += m; std::cout << r << '\n'; } }