#include using namespace std; #ifdef LOCAL_ void debug_out() { cerr << "\033[0m" << endl; } template void debug_out(Head H, Tail... T) { cerr << ' ' << H << ','; debug_out(T...); } #define debug(...) cerr << "\033[1;36m" << __func__ << ":L" << __LINE__ << " " << #__VA_ARGS__ << ":", debug_out(__VA_ARGS__) #define dump(x) cerr << __func__ << ":L" << __LINE__ << " " << #x << " = " << (x) << endl #else #define debug(...) (void(0)) #define dump(x) (void(0)) #endif #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define irep(i, n) for (int i = (int)(n)-1; i >= 0; --i) using ll = long long; using pii = pair; using pil = pair; using pli = pair; using pll = pair; constexpr int INF = 1000'000'000; constexpr long long HINF = 4000'000'000000'000'000; constexpr long long MOD = 1000000007; // = 998244353; constexpr double EPS = 1e-4; constexpr double PI = 3.14159265358979; #pragma region Macros template ostream &operator<<(ostream &os, const pair &p) { os << '(' << p.first << ',' << p.second << ')'; return os; } template ostream &operator<<(ostream &os, const vector &v) { os << '['; for (auto &e : v) { os << e << ','; } os << ']'; return os; } template ostream &operator<<(ostream &os, const set &st) { os << '{'; for (auto itr = st.begin(); itr != st.end(); itr++) { os << *itr << ','; } os << '}'; return os; } template ostream &operator<<(ostream &os, const map &mp) { os << '{'; for (auto itr = mp.begin(); itr != mp.end(); itr++) { os << itr->first << ": " << itr->second << ','; } os << '}'; return os; } void yn(bool cond, string Yes = "Yes", string No = "No") { cout << (cond ? Yes : No) << '\n'; } template bool chmax(T &x, const T &y) { return (x < y) ? (x = y, true) : false; } template bool chmin(T &x, const T &y) { return (x > y) ? (x = y, true) : false; } #pragma endregion // gcd // 非負整数a,bの最大公約数を求める. // 制約: a,b >= 0 // 計算量: O(logmax(a,b)) template T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); } // lcm // 非負整数a,bの最小公倍数を求める. // 制約: a,b >= 0 // 計算量: O(logmax(a,b)) template T lcm(T a, T b) { return a / gcd(a, b) * b; } // ext_gcd // 拡張Euclidの互除法で非負整数a,bに対してax + by = gcd(a,b)を満たす整数x,yを求める. // 出力される値は xy != 0 ならば |x| <= b,|y| <= a を満たす. // 制約: a,b >= 0 // 計算量: O(logmax(a,b)) template pair ext_gcd(T a, T b) { if (b == 0) { return make_pair(1, 0); } auto [x, y] = ext_gcd(b, a % b); return make_pair(y, x - a / b * y); } // pow_mod // x^k mod mを計算する. // 計算量: O(logk) template T pow_mod(T x, long long k, int m) { T ret = T(1); while (k > 0) { if (k & 1) { ret *= x; ret %= m; } k >>= 1; x *= x; x %= m; } return ret; } // inv_mod // ax = 1 (mod m) なるx (0 <= x < m)が存在するならば // それを返し, 存在しなければ-1を返す. // 計算量: O(log|max(a,m)|) template T inv_mod(T a, T m) { auto [x, y] = ext_gcd(a, m); T g = a * x + m * y; if (g != 1) return -1; return (m + x % m) % m; } // linear_congruence // forall i,A_i x = B_i mod M_i <=> x = b mod m // とかけるときに(b,m)の組を返す. ただし(0 <= b < m)をみたす. このように書けない時は(-1,-1)を返す. // 計算量: O(nlogmax|M_i|),nは式の数 template pair linear_congruence(const vector &A, const vector &B, const vector &M) { T x = 0, m = 1; for (int i = 0; i < (int)A.size(); i++) { T a = A[i] * m, b = B[i] - A[i] * x, d = gcd(M[i], a); if (b % d != 0) return make_pair(-1, -1); T t = b / d * inv_mod(a / d, M[i] / d) % (M[i] / d); x += m * t; m *= M[i] / d; } return make_pair((m + x % m) % m, m); } // garner // forall i, x = B_i mod M_i <=> x = b mod m // とかけるときに(b,m)の組を返す. ただし(0 <= b < m)をみたす. このように書けない時は(-1,-1)を返す. // 計算量: O(nlogmax|M_i|),nは式の数 template pair garner(const vector &R, const vector &M) { vector A(R.size(), 1); return linear_congruence(A, R, M); } // aのk乗根を求める long long root_int(long long a, int k) { if (k == 0) return 0; long long x = pow(a, (double)1.0 / k); while (pow(x, k) > a) x--; while (pow(x + 1, k) <= a) x++; return x; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); vector X(3), Y(3); rep(i, 3) cin >> X[i] >> Y[i]; auto [x, m] = garner(X, Y); if (x == 0) cout << m << '\n'; else cout << x << '\n'; return 0; }