結果

問題 No.186 中華風 (Easy)
ユーザー chigu314chigu314
提出日時 2021-05-05 16:33:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,910 bytes
コンパイル時間 2,580 ms
コンパイル使用メモリ 206,500 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-13 10:38:56
合計ジャッジ時間 2,994 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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> b(3),m(3);
  bool zero=false;
  rep(i,3) {
    cin>>b[i]>>m[i];
    if(b[i]) zero=true;
  }
  pair<ll,ll> mio=ChineseRem(b,m);
  if (mio.second == -1) cout << -1 << "\n";
  else if(zero) cout << mio.first << "\n";
  else cout << mio.second << "\n";
}
/*制約を確認しろllじゃなくて大丈夫か？*/
0