結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー Ricky_pon
提出日時 2023-06-27 10:13:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,024 bytes
コンパイル時間 772 ms
コンパイル使用メモリ 78,296 KB
最終ジャッジ日時 2025-02-15 02:35:12
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;
using lint = ll;
using ulint = unsigned long long;
using pii = pair<int, int>;
using pll = pair<lint, lint>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
#define FOR(i, a, b) for (int i = int(a); i < int(b); ++i)
#define rep(i, n) FOR(i, 0, n)
template <class T, class U>
bool chmin(T &a, U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T, class U>
bool chmax(T &a, U &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
ostream &operator<<(ostream &os, const V<T> &v) {
    os << "[";
    for (auto d : v) os << d << ", ";
    return os << "]";
}

struct EG {
    lint g, x, y;
};
EG ext_gcd(ll a, ll b) {
    if (b == 0) {
        if (a >= 0) {
            return EG{a, 1, 0};
        } else {
            return EG{-a, -1, 0};
        }
    }
    auto e = ext_gcd(b, a % b);
    return EG{e.g, e.y, e.x - a / b * e.y};
}

lint inv_mod(ll x, ll md) {
    auto z = ext_gcd(x, md).x;
    return (z % md + md) % md;
}

lint pow_mod(lint x, lint n, lint mod) {
    auto r = 1 % mod;
    x %= mod;
    while (n) {
        if (n & 1) r = (r * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return r;
}

pll crt(const V<ll> &rs, const V<ll> ms) {
    int n = int(rs.size());
    ll r = 0, m = 1;
    rep(i, n) {
        auto [g, im, _] = ext_gcd(m, ms[i]);
        if ((rs[i] - r) % g) return {0, -1};
        auto tmp = (rs[i] - r) / g * im % (ms[i] / g);
        r += m * tmp;
        m *= ms[i] / g;
    }
    return {(r % m + m) % m, m};
}

int main() {
    vector<lint> rs(3), ms(3);
    rep(i, 3) cin >> rs[i] >> ms[i];
    auto [r, m] = crt(rs, ms);
    if (m < 0) {
        puts("-1");
        return 0;
    }
    if (r == 0) {
        r = 1;
        rep(i, 3) r = r / gcd(r, ms[i]) * ms[i];
    }
    cout << r << endl;
}
0