結果
問題 | No.186 中華風 (Easy) |
ユーザー |
![]() |
提出日時 | 2019-12-27 17:11:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,243 bytes |
コンパイル時間 | 1,711 ms |
コンパイル使用メモリ | 169,668 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-19 18:37:26 |
合計ジャッジ時間 | 2,579 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template<typename T> using V = vector<T>; template<typename T> using VV = vector<vector<T>>; #define fs first #define sc second #define rep(i,a,n) for(ll i=a;i<(ll)(n);++i) #define ENDL '\n' typedef pair<ll,ll> PL; template<typename T> T extgcd(T a,T b,T &x,T &y){ if(!b){x=1;y=0;return a;} T d=extgcd(b,a%b,y,x); y-=(a/b)*x; return d; } //ax+by=gcd(a,b)を満たすx,y 返り値はgcd template<typename T> pair<T,T> ChineseRem(const vector<T> &b,const vector<T> &m){ T r=0,M=1; for(int i=0;i<(int)m.size();++i){ T p,q; T g=extgcd(M,m[i],p,q); if((b[i]-r)%g)return {0,-1}; r+=M*(((b[i]-r)/g*p)%(m[i]/g)); M*=m[i]/g; } return {(r%M+M)%M,M}; } //x=a[i](modm[i]) を満たすx(0<=x<Π(m[i])) を求める //法が互いに素でない場合、解が存在しない場合がある signed main(){ cin.tie(0);ios::sync_with_stdio(false); cout<<fixed<<setprecision(20); V<ll> x(3),y(3); rep(i,0,3){ cin>>x[i]>>y[i]; } PL p=ChineseRem(x,y); if(p.sc==-1)cout<<-1<<ENDL; else{ if(p.fs)cout<<p.fs<<ENDL; else cout<<p.sc<<ENDL; } } //( ・ __ ・ ) KEEP BEING ORGANIZED //CHECK overflow,vector_size,what to output?