#include #include #include #include using namespace std; typedef long long ll; ll gcd(ll a, ll b) { if (a % b == 0)return b; return gcd(b, a % b); } ll lcm(ll a, ll b) { return a * b / gcd(a, b); } //e_gcd()自体はaとbの最大公約数を返す。 //xとyは、a*x+b*y=gcd(a,b)となる(x,y)の1つの組を返す。 //a*x+b*y=gcdの時、a=b*p+(a%b)を代入して、b*p*x+(a%b)*x+b*y=b*(p*x+y)+(a%b)*x //次のx->p*x+y //次のy->x //次のa->b //次のb->a%b ll e_gcd(ll a, ll b, ll& x, ll& y) { if (b == 0) { x = 1; y = 0; return a; } ll gcd_res = e_gcd(b, a % b, x, y); ll p = a / b; ll nx = x, ny = y; x = ny; y = nx - p * x; return gcd_res; } std::pair CRT_Simple(const vector& val, const vector& mod) { //x == val[i] (mod[i])がn本ある感じ if (val.size() != mod.size())return make_pair(-1, -1); int n = val.size(); ll x = 0;//最初は0 (mod 1)で始める。 ll mlcm = 1; for (int i = 0; i < n; i++) { //m[i] % mgcdが等しくない場合は、解がない。 ll p, q; ll mgcd = e_gcd(mlcm, mod[i], p, q);//pとqの符号は逆になる if ((val[i] - x) % mgcd != 0) { return make_pair(-1, -1); } //実際のpを求め(e_gcdのは右辺がgcd(mlcm, mod[i])でval[i]-xと定数倍の差がある。 //その差を補正して、mod[i] / mgcdであまりを取ると正で一番小さいpを得られる。 ll min_p = (p * (val[i] - x) / mgcd) % (mod[i] / mgcd); x += min_p * mlcm;//これはpでの計算 //以下のようにqで求めてもいい。 //ll min_q = (q * (val[i] - x) / mgcd) % (mlcm / mgcd); //x = val[i] - min_q * mod[i]; mlcm = lcm(mlcm, mod[i]); } x %= mlcm; return make_pair(x, mlcm); } int main() { ll X1, X2, X3, Y1, Y2, Y3; cin >> X1 >> Y1 >> X2 >> Y2 >> X3 >> Y3; auto ret = CRT_Simple({ X1, X2, X3 }, { Y1, Y2, Y3 }); if (ret.first == -1) { cout << -1 << endl; return 0; } cout << ret.first << endl; return 0; }