結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー chigu314
提出日時 2021-05-05 16:18:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,919 bytes
コンパイル時間 2,001 ms
コンパイル使用メモリ 201,480 KB
最終ジャッジ日時 2025-01-21 07:31:04
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define all(V) V.begin(),V.end()
#define pi 3.1415926535897932384626
#define fi fixed<<setprecision(13)
#define MOD 1000000007
#define ll long long 
#define rep(i, n) for (int i = 0; i < (ll)(n); i++)
#define Rep(i, n) for (ll i = 1; i <=(ll)(n); i++)
#define reps(i,k,n) for (ll i = (ll)k; i < (ll)(n); i++)
using namespace std;
using V = vector<vector<int>>;
using P = pair<int,int>;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
template<class T> void chmin(T& a,T b){ if(a > b) a=b; }
template<class T> void chmax(T& a,T b){ if(a < b) a=b; }
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){fill( (T*)array, (T*)(array+N), val );}
const ll infll=1LL<<62;
const ll inf=1<<30;
struct Edge{
  int to;
  ll w;
  Edge(int to,ll w) : to(to),w(w){}
};
using Graph = vector<vector<Edge>>;
inline ll mod(ll a, ll m) {
    return (a % m + m) % m;
}
//拡張Euclid
ll extGcd(ll a, ll b, ll &p, ll &q) {  
    if (b == 0) { p = 1; q = 0; return a; }  
    ll d = extGcd(b, a%b, q, p);  
    q -= a/b * p;  
    return d;  
}
// 中国剰余定理
pair<ll,ll> ChineseRem(const vector<ll> &b, const vector<ll> &m) {
  ll r = 0, M = 1;
  rep(i,b.size()) {
    ll p, q;
    ll d = extGcd(M, m[i], p, q);
    if ((b[i] - r) % d != 0) return make_pair(0, -1);
    ll tmp = (b[i] - r) / d * p % (m[i]/d);
    r += M * tmp;
    M *= m[i]/d;
  }
  return make_pair(mod(r, M), M);
}
int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  /*----------------------------------------------*/
  vector<ll> a(3),b(3);
  bool zero=false;
  rep(i,3) {
    cin>>a[i]>>b[i];
    if(b[i]) zero=1;
  }
  pair<ll,ll> mio=ChineseRem(a,b);
  if (mio.second == -1) cout << -1 << endl;
  else if(zero) cout << mio.first << endl;
  else cout << mio.second << endl;
  return 0;
}
/*制約を確認しろllじゃなくて大丈夫か？*/
0