//自明なケース:Xi = 0, □には0, lcm(y1, y2, y3), …が入る。 -> 気づき:□に当てはまる数はlcm(y1,y2,y3)周期で, 最小値はlcm(y1,y2,y3)未満 //「気づき」を使って, (0,1) -> (0,1) && (x1,y1) -> (0,1) && (x1,y1) && (x2,y2) -> …と求めていくと簡単. //lcm(y1, y2) / lcm(y1, y2, y3) <= y3とかそんな感じで高々10^6オーダーなことは示せる。 #include #define int long long using namespace std; int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); } int lcm(int a, int b) { return a * b / gcd(a, b); } signed main() { int x[3], y[3]; int i, j; for (i = 0; i < 3; i++) cin >> x[i] >> y[i]; int ans = 0; int t = 1; for (i = 0; i < 3; i++) { for (j = ans; j % y[i] != x[i] && j < y[i] * t; j += t); if (j >= y[i] * t) { cout << -1 << endl; return 0; } ans = j; t = lcm(t, y[i]); } cout << ans << endl; return 0; }