結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー ta7uw
提出日時 2020-09-22 15:19:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,316 bytes
コンパイル時間 1,726 ms
コンパイル使用メモリ 172,820 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-26 04:31:41
合計ジャッジ時間 2,501 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
// #include <atcoder/all>

using namespace std;
// using namespace atcoder;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG
/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#else
#define print(...)
#endif

inline long long mod(long long a, long long m) {
    return (a % m + m) % m;
}

/**
 * 拡張 Euclid の互除法
 * @return ap + bq = gcd(a, b) となる (p, q) を求め、d = gcd(a, b) をリターンします
 */
long long extGcd(long long a, long long b, long long &p, long long &q) {
    if (b == 0) {
        p = 1;
        q = 0;
        return a;
    }
    long long d = extGcd(b, a % b, q, p);
    q -= a / b * p;
    return d;
}

/**
 * Chinese remainder theorem (中国剰余定理)
 * ref. https://qiita.com/drken/items/ae02240cd1f8edfc86fd
 * @return リターン値を (r, m) とすると解は x ≡ r (mod. m), 解なしの場合は (0, -1) をリターン
 */
pair<long long, long long> chinese_remainder_theorem(const vector<long long> &b, const vector<long long> &m) {
    long long r = 0, M = 1;
    for (int i = 0; i < (int) b.size(); ++i) {
        long long p, q;
        long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)
        if ((b[i] - r) % d != 0) return make_pair(0, -1);
        long long tmp = (b[i] - r) / d * p % (m[i] / d);
        r += M * tmp;
        M *= m[i] / d;
    }
    return make_pair(mod(r, M), M);
}


void solve() {
    ll X1, Y1, X2, Y2, X3, Y3;
    cin >> X1 >> Y1 >> X2 >> Y2 >> X3 >> Y3;
    vector<ll> b = {X1, X2, X3};
    vector<ll> m = {Y1, Y2, Y3};
    auto ans = chinese_remainder_theorem(b, m);
    if (ans.first == 0) {
        cout << -1 << '\n';
    } else {
        cout << ans.first << '\n';
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}
0