#define PROBLEM "https://yukicoder.me/problems/no/186" #include using namespace std; tuple ext_gcd(long long a, long long b) { if(b == 0) return {a, 1, 0}; auto [d, y, x] = ext_gcd(b, a % b); y -= a / b * x; return {d, x, y}; } inline long long safe_mod(long long a, long long m) { return (a % m + m) % m; } pair crt(const vector& b, const vector& m) { assert(b.size() == m.size()); long long r = 0, M = 1; for(int i = 0; i < (int)b.size(); i++) { auto [d, p, q] = ext_gcd(M, m[i]); if((b[i] - r) % d != 0) return {0, -1}; long long tmp = (b[i] - r) / d * p % (m[i] / d); r += M * tmp; M *= m[i] / d; } r = safe_mod(r, M); return {r, M}; } int main() { vector X(3), Y(3); for(int i = 0; i < 3; i++) { cin >> X[i] >> Y[i]; } auto [r, m] = crt(X, Y); if(r) cout << r << endl; else cout << -1 << endl; return 0; }