#pragma GCC optimize("O3") #pragma GCC target("sse4") #include #include #include #include #include #include #include #include #include #include #include #include using namespace atcoder; // #include // #include #include // ヘッダファイルインクルード #include using namespace std; // 名前空間指定 using namespace std; using mint = modint998244353; // using Graph = vector>; // 重みなしのグラフ // struct Edge { // int to; // long long w; // Edge(int to, long long w) : to(to), w(w) {} // }; // using Graph_w = vector>; // 重み付きのグラフ // using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef pair pi; typedef pair pl; typedef pair pd; typedef vector vi; typedef vector vd; typedef vector vl; typedef vector vpi; typedef vector vpl; template #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define F0R(i, a) for (int i = 0; i < (a); i++) #define FORd(i, a, b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define shandom_ruffle random_shuffle const int MOD = 1000000007; const int inf = pow(10, 9); const ll INF = 1e18; const int MX = 100001; // check the limits, dummy const ll infl = 1LL << 60; template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } template void print(const vector v) { cout << "[ "; F0R(i, v.size()) { cout << v[i] << ' '; } cout << "]" << '\n'; } // 負の数にも対応した mod // 例えば -17 を 5 で割った余りは本当は 3 (-17 ≡ 3 (mod. 5)) // しかし単に -17 % 5 では -2 になってしまう inline long long mod(long long a, long long m) { return (a % m + m) % m; } long long gcd(long long a, long long b) { if (b == 0) { return a; } else { return gcd(b, a % b); } } /* lcm (a, b) : 2整数版 入力:整数 a, b 出力:aとbの最小公倍数 */ long long lcm(long long a, long long b) { long long d = gcd(a, b); return a / d * b; } // // Union-Find // struct UnionFind { // vi par, siz; // // 初期化 // UnionFind(int n) : par(n, -1), siz(n, -1) {} // // 根を求める // int root(int x) { // if (par[x] == -1) // return x; // else // return par[x] = root(par[x]); // } // // xとyが同じグループに属するか // bool issame(int x, int y) { return root(x) == root(y); } // // xのグループとyのグループを併合する // bool unite(int x, int y) { // x = root(x); // y = root(y); // if (x == y) return false; // if (siz[x] > siz[y]) swap(x, y); // par[y] = x; // siz[x] += siz[y]; // return true; // } // // xのグループのサイズ // int size(int x) { return siz[root(x)]; } // // 入力サンプル // int N, M; // cin >> N >> M; // vpi Edge(M); // for (int i = 0; i < M; i++) { // int a, b; // cin >> a >> b; // Edge[i].first = a - 1; // Edge[i].second = b - 1; // } // } // ; // // 深さ優先探索 再帰ver // vector seen; // void dfs(const Graph &G, int v) { // seen[v] = true; // v を訪問済にする // // v から行ける各頂点 next_v について // for (auto next_v : G[v]) { // if (seen[next_v]) continue; // next_v が探索済だったらスルー // dfs(G, next_v); // 再帰的に探索 // } // } // // 入力: グラフ G と,探索の始点 s // // 出力: s から各頂点への最短路長を表す配列 // vector bfs(const Graph &G, int s) { // int N = (int)G.size(); // 頂点数 // vector dist(N, -1); // 全頂点を「未訪問」に初期化 // queue que; // // 初期条件 (頂点 s を初期頂点とする) // dist[s] = 0; // que.push(s); // s を橙色頂点にする // // BFS 開始 (キューが空になるまで探索を行う) // while (!que.empty()) { // int v = que.front(); // キューから先頭頂点を取り出す // que.pop(); // // v からたどれる頂点をすべて調べる // for (int x : G[v]) { // // すでに発見済みの頂点は探索しない // if (dist[x] != -1) continue; // // 新たな白色頂点 x について距離情報を更新してキューに挿入 // dist[x] = dist[v] + 1; // que.push(x); // } // } // return dist; // } // // トポロジカルソート(幅優先) // vector topo_sort(const Graph &G) { // bfs // vector ans; // int n = (int)G.size(); // vector ind(n); // ind[i]: 頂点iに入る辺の数(次数) // for (int i = 0; i < n; i++) { // 次数を数えておく // for (auto e : G[i]) { // ind[e]++; // } // } // queue que; // for (int i = 0; i < n; i++) { // 次数が0の点をキューに入れる // if (ind[i] == 0) { // que.push(i); // } // } // while (!que.empty()) { // 幅優先探索 // int now = que.front(); // ans.push_back(now); // que.pop(); // for (auto e : G[now]) { // ind[e]--; // if (ind[e] == 0) { // que.push(e); // } // } // } // return ans; // } // -------------------------------------------------------- // This is tool // -------------------------------------------------------- long long extGcd(long long a, long long b, long long &p, long long &q) { if (b == 0) { p = 1; q = 0; return a; } long long d = extGcd(b, a % b, q, p); q -= a / b * p; return d; }; // 中国剰余定理 // リターン値を (r, m) とすると解は x ≡ r (mod. m) // 解なしの場合は (0, -1) をリターン pair ChineseRem(const vector &b, const vector &m) { long long r = 0, M = 1; for (int i = 0; i < (int)b.size(); ++i) { long long p, q; long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d) if ((b[i] - r) % d != 0) return make_pair(0, -1); long long tmp = (b[i] - r) / d * p % (m[i] / d); r += M * tmp; M *= m[i] / d; } return make_pair(mod(r, M), M); }; void Main() { ios_base::sync_with_stdio(0); cin.tie(0); vl x(3), y(3); F0R(i, 3) { cin >> x[i] >> y[i]; } pair res = ChineseRem(x, y); if (res == make_pair(0 * 1LL, -1 * 1LL)) cout << -1 << endl; else cout << res.first << endl; // cout << "x ≡ " << res.first << " (mod. " << res.second << ")" << endl; } int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(15); Main(); } // わかりやすかったやつ // https://atcoder.jp/contests/abc287/submissions/38502994