#include #include #include // Find x and y such that a*x + b*y = gcd(a, b) // Return gcd(a, b) long long extgcd(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1, y = 0; return a; } long long ret = extgcd(b, a%b, x, y); std::tie(x, y) = std::make_pair(y, x - a / b * y); return ret; } // Chinese Remainder Theorem // Find rem such that 0 <= rem < lcm(m1, m2) and // rem % m1 = r1 and rem % m2 = r2 // Return { -1, -1 } if such rem doesn't exist, // otherwise return { lcm(m1, m2), rem } std::pair crt(long long m1, long long r1, long long m2, long long r2) { long long x = 0, y = 0; long long d = extgcd(m1, m2, x, y); if (r1%d != r2%d) { return { -1, -1 }; } long long lcm = m1 / d * m2; long long rem = ((r2 - r1) / d * x % (m2 / d)) * m1; rem = ((rem + r1) % lcm + lcm) % lcm; return { lcm, rem }; } int main() { long long x, y; std::cin >> x >> y; for (int i = 0; i < 2; i++) { long long a, b; std::cin >> a >> b; std::tie(y, x) = crt(y, x, b, a); if (x == -1) { std::cout << -1 << std::endl; return 0; } } std::cout << x << std::endl; return 0; }