結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー sahiya
提出日時 2020-12-21 03:56:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,688 bytes
コンパイル時間 1,595 ms
コンパイル使用メモリ 112,192 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-21 12:39:28
合計ジャッジ時間 2,300 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstring>
#include <deque>
#include <forward_list>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef bitset<16> BS;
struct edge {
    int to, cost, id;
};
const ll MOD = 1E+09 + 7; // =998244353;
const ll INF = 1E18;
const int MAX_N = 3;

ll dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

ll extgcd(ll a, ll b, ll& x, ll& y);
pair<ll, ll> crt(ll b1, ll m1, ll b2, ll m2);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll r = 0, m = 1;
    bool all0 = true;
    for (int i = 1; i <= 3; i++) {
        ll x, y;
        cin >> x >> y;
        if (x != 0)
            all0 = false;
        auto p = crt(r, m, x, y);
        r = p.first, m = p.second;
        //cout << "r = " << r << ", m = " << m << "\n";
    }

    /*
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << "i = " << i << ", j = " << j << ", dp = " << dp[i][j] << "\n";
        }
    }
    */
    if (m == -1) {
        cout << -1 << "\n";
    } else if (!all0) {
        cout << r << "\n";
    } else {
        cout << m << "\n";
    }

    return 0;
}

// ax + by = gcd(a,b) を満たす(x,y)を求める
ll extgcd(ll a, ll b, ll& x, ll& y)
{
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

//中国剰余定理
//x ≡ b1(mod.m1) かつ x ≡ b2(mod.m2) をみたすような x が存在するとき
//x ≡ r(mod.lcm(m1, m2)) をみたすような r が lcm(m1, m2) 未満に一つだけ存在する。
//b1, m1, b2, m2 を入力として r と lcm(m1, m2) のペアを返す。
//ただし条件を満たす x が存在するのは b1 ≡ b2(mod.gcd(m1, m2)) の場合に限るため、
//解が存在しない場合には (0, -1) のペアを返す
pair<ll, ll> crt(ll b1, ll m1, ll b2, ll m2)
{
    if (m1 < 0 || m2 < 0)
        return make_pair(0, -1);
    ll p, q;
    ll d = extgcd(m1, m2, p, q);
    if ((b2 - b1) % d != 0)
        return make_pair(0, -1);
    ll s = (b2 - b1) / d;
    ll m = m1 * m2 / d;
    //桁あふれ対策
    ll _x = (s * p) % (m2 / d);
    ll x = b1 + m1 * _x;
    // x < 0 の可能性があるため x >= 0 を満たす最小の x を r とする
    ll r = (x % m + m) % m;
    return make_pair(r, m);
}
0