結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー tubo28
提出日時 2015-10-23 21:05:34
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,543 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,196 ms
コンパイル使用メモリ 172,516 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-08 16:03:56
合計ジャッジ時間 2,185 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cassert>
#include <tuple>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef __int128_t lll;

// x, mod
pair<lll,lll> crt(lll a1, lll m1, lll a2, lll m2){
    auto normal = [](lll x, lll m){
        return x >= -x ? x%m : m - (-x)%m;
    };
    auto myMul = [&normal](lll a, lll b, lll m){
        return normal(a,m) * normal(b,m) % m;
    };
    auto extgcd = [](lll a, lll b, lll &x, lll &y) {
        for(lll u = y = 1, v = x = 0; a; ) {
            lll q = b / a;
            swap(x -= q*u, u);
            swap(y -= q*v, v);
            swap(b -= q*a, a);
        }
        return b;
    };
    lll k1,k2;
    lll g = extgcd(m1, m2, k1, k2);
    if(normal(a1,g) != normal(a2,g)){
        return make_pair(-1, -1);
    } else {
        lll l = m1 / g * m2;
        lll x = a1 + myMul(myMul((a2 - a1) / g, k1, l) , m1, l);
        return make_pair(x,l);
    }
}

pair<lll,lll> crt(vector<lll> a, vector<lll> m){
    lll mod = 1, ans = 0;
    int n = a.size();
    for(int i = 0; i < n; i++){
        tie(ans,mod) = crt(ans, mod, a[i], m[i]);
        if(ans == -1) return make_pair(-1, -1);
    }
    return make_pair(ans,mod);
}

int main(){
    int n = 3;
    while(1){
        vector<lll> x(n), y(n);
        for(int i = 0; i < n; i++){
            ll xx,yy;
            if(!(cin >> xx >> yy)) exit(0);
            x[i] = xx, y[i] = yy;
        }
        lll ans,m;
        tie(ans,m) = crt(x,y);
        if(ans == 0) ans = m;
        cout << (ll)ans << endl;
    }
}
0