結果
問題 |
No.187 中華風 (Hard)
|
ユーザー |
![]() |
提出日時 | 2020-09-26 22:49:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,601 bytes |
コンパイル時間 | 3,890 ms |
コンパイル使用メモリ | 230,868 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-30 17:16:49 |
合計ジャッジ時間 | 4,682 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 WA * 22 RE * 2 |
コンパイルメッセージ
main.cpp:17: warning: "DEBUG" redefined 17 | #define DEBUG(x) std::cerr << #x << " : " << (x) << std::endl; | main.cpp:16: note: this is the location of the previous definition 16 | #define DEBUG(x) ; |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; using P = pair<ll, ll>; const ll MOD = 1e9+7; // const ll MOD = 998244353; const ll INF = 1ll<<60; #define FOR(i,a,b) for (ll i=(a);i<(ll)(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() #define DEBUG(x) ; #define DEBUG(x) std::cerr << #x << " : " << (x) << std::endl; int dx[4]{0, 1, 0, -1}; int dy[4]{1, 0, -1, 0}; //////////////////// // Chinese remainder theorem inline ll mod(ll a, ll m) { a %= m; if (a < 0) a += m; return a; } 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; for (ll i = 0; i < (int)b.size(); ++i) { ll p, q; ll d = extGcd(M, m[i], p, q); if ((b[i] - r) % d != 0) return {0, -1}; ll tmp = (b[i] - r) / d * p % (m[i]/d); r += M * tmp; M *= m[i]/d; } return {mod(r, M), M}; } // Chinese remainder theorem // x = b_0(mod, m_0) // x = b_1(mod, m_1) // ... // x = b_N-1(mod, m_N-1) // <=> // x = r(mod, m) // // call : ChineseRem(vector<ll>b, vector<ll>) // return : pair<ll, ll>(x, m) // return(no solution) : pair<ll, ll>(0, -1) int main(int argc, char **argv) { ios_base::sync_with_stdio(false); cin.tie(NULL); ll N; N = 3; vector<ll> X(N), Y(N); REP(i, N) cin >> X[i] >> Y[i]; auto res = ChineseRem(X, Y); if (res == P{0, -1}) { std::cout << -1 << std::endl; } else std::cout << res.first << std::endl; return 0; }