This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub mugen1337/procon
#define PROBLEM "https://yukicoder.me/problems/447" #include "../template.hpp" #include "../Math/Garner.hpp" signed main(){ vector<ll> r(3),m(3); rep(i,3) cin>>r[i]>>m[i]; auto p=Garner(r,m); if(p.second==0) cout<<-1<<endl; else if(p.first==0) cout<<p.second<<endl; else cout<<p.first<<endl; return 0; }
#line 1 "test/yuki447.test.cpp" #define PROBLEM "https://yukicoder.me/problems/447" #line 1 "template.hpp" #include<bits/stdc++.h> using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define mod 1000000007 using ll=long long; const int INF=1000000000; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct IOSetup{ IOSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(12); } } iosetup; template<typename T> ostream &operator<<(ostream &os,const vector<T>&v){ for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" "); return os; } template<typename T> istream &operator>>(istream &is,vector<T>&v){ for(T &x:v)is>>x; return is; } #line 4 "test/yuki447.test.cpp" #line 1 "Math/Garner.hpp" // (val, mod) pair<ll,ll> Garner(const vector<ll> &rems,const vector<ll> &mods){ // {g, x}, g=gcd(a,b), xa = g (mod b) function<pair<ll,ll>(ll,ll)> gcd_inv=[](ll a,ll b){ a%=b; if(a<0) a+=b; if(a==0) return make_pair(b,0ll); ll s=b,t=a,m0=0,m1=1; while(t){ ll u=s/t; s-=t*u,m0-=m1*u; swap(s,t); swap(m0,m1); } if(m0<0) m0+=b/s; return make_pair(s,m0); }; ll R=0,M=1; for(int i=0;i<(int)rems.size();i++){ ll r=rems[i],m=mods[i]; r%=m;if(r<0) r+=m; if(m>M) swap(m,M),swap(r,R); if(M%m==0){ if(R%m!=r) return {0,0}; continue; } auto [g,iM]=gcd_inv(M,m); ll u=m/g; if((r-R)%g) return {0,0}; ll x=(r-R)/g%u*iM%u; R+=x*M; M*=u; if(R<0) R+=M; } return {R,M}; } #line 6 "test/yuki447.test.cpp" signed main(){ vector<ll> r(3),m(3); rep(i,3) cin>>r[i]>>m[i]; auto p=Garner(r,m); if(p.second==0) cout<<-1<<endl; else if(p.first==0) cout<<p.second<<endl; else cout<<p.first<<endl; return 0; }