#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; // 最大公約数 long long gcd(long long a, long long b){ while(b != 0){ long long tmp = a % b; a = b; b = tmp; } return a; } // a,b の最大公約数と、ax + by = gcd(a,b) となる x,y を求める long long extgcd(long long a, long long b, long long &x, long long &y) { long long g = a; if(b != 0){ g = extgcd(b, a % b, y, x); y -= (a / b) * x; }else{ x = 1; y = 0; } return g; } // ax ≡ gcd(a, m) (mod m) となる x を求める // a, m が互いに素ならば、関数値は mod m での a の逆数となる long long mod_inverse(long long a, long long m) { long long x, y; extgcd(a, m, x, y); return (x % m + m) % m; } // 連立線形合同式 a[i] * x ≡ b[i] (mod m[i]) を解く pair ChineseRemainderTheorem(const vector& a, const vector& b, const vector& m) { pair ret(0, 1); for(unsigned i=0; i x(3), y(3); for(int i=0; i<3; ++i) cin >> x[i] >> y[i]; auto p = ChineseRemainderTheorem(vector(3, 1), x, y); if(p.first == 0) p.first += p.second; cout << p.first << endl; return 0; }