#include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<stack> #include<numeric> #include<queue> #include<cmath> #include<deque> #include<cassert> using namespace std; typedef long long ll; const ll MOD=1e9+7; const ll INF=1LL<<60; //ax+by=gcd(a,b) tuple<ll,ll,ll> ext_gcd(ll a,ll b){ //cout<<"a="<<a<<",b="<<b<<endl; if(b==0){ //a*1+b*0 = a return make_tuple(a,1,0); } auto [g,x,y]=ext_gcd(b,a%b); //cout<<"g="<<g<<",x="<<x<<",y="<<y<<endl; return make_tuple(g,y,x-(a/b)*y); } /* ll chinese_rem(ll b1,ll m1,ll b2, ll m2){ //d=m1*p+m2*q auto [d,p,q] = ext_gcd(m1,m2); //cout<<"d="<<d<<",p="<<p<<",q="<<q<<endl; ll lcm=(m1/d)*m2; ll c=(b2-b1)/d; c%=lcm; if(b2<b1){ c*=(-1); } ll t=m1*c%lcm; p%=lcm; if(p<0){ p+=lcm; p%=lcm; } t*=p;//pが負の数の可能性があるので t%=lcm; ll x=b1+t; x%=lcm; return x; }; */ ll chinese_rem(ll b1,ll m1,ll b2, ll m2){ //d=m1*p+m2*q auto [d,p,q] = ext_gcd(m1,m2); //cout<<"d="<<d<<",p="<<p<<",q="<<q<<endl; ll lcm=(m1/d)*m2; ll c=(b2-b1)/d; //c%=lcm; c*=p; c%=(m2/d); c*=m1; c%=lcm; ll x=b1+c; x%=lcm; x+=lcm; x%=lcm; return x; }; ll gcd(ll x,ll y){ return y==0?x:gcd(y,x%y); } ll lcm(ll x,ll y){ return x/gcd(x,y)*y; } /* ll chinese_rem2(const vector<ll>& b,const vector<ll>& m){ assert(b.size()==m.size()); int n=b.size(); ll m0=1; ll x=0; ll lcmm=1; for(int i=0;i<n;i++){ x=chinese_rem(x,lcmm,b[i],m[i]); lcmm=lcm(lcmm,m[i]); x%=lcmm; if(x<0){ x+=lcmm; x%=lcmm; } x%=lcmm; } cout<<"lcmm="<<lcmm<<endl; return x%lcmm; } */ pair<ll,ll> chinese_rem2(const vector<ll>& b,const vector<ll>& m){ assert(b.size()==m.size()); int n=b.size(); ll x=0; ll M=1; for(int i=0;i<n;i++){ //p*lcmm + q*m[i]=g auto [g,p,q]=ext_gcd(M,m[i]); if( (b[i]-x)%g!=0 ) return make_pair(-1,0); ll c=( ((b[i]-x)/g)*p )%(m[i]/g); x+=M*c; M*=m[i]/g; } // x=x%M+M; // x%=M; //cout<<"lcmm="<<lcmm<<endl; return make_pair((x%M + M)%M ,M); } int main(){ //cout<<chinese_rem(2,3,3,5)<<endl; vector<ll> b(3); vector<ll> m(3); for(int i=0;i<3;i++){ cin>>b[i]>>m[i]; } auto [ans,l]=chinese_rem2(b,m); //cout<<"ans="<<ans<<endl; cout<<ans<<endl; /* ll lcmresult=1; for(ll c:m){ lcmresult = lcm(lcmresult,c); } cout<<"lcmresult="<<lcmresult<<endl; */ }