結果

問題 No.186 中華風 (Easy)
ユーザー tubo28
提出日時 2015-10-23 21:05:34
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 4 ms
コード長 1,543 Byte
コンパイル時間 607 ms
使用メモリ 3,012 KB
最終ジャッジ日時 2019-04-24 22:53:40

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0.in AC 3 ms
3,008 KB
1.in AC 3 ms
3,012 KB
2.in AC 3 ms
3,012 KB
3.in AC 3 ms
3,012 KB
4.in AC 4 ms
3,012 KB
5.in AC 2 ms
3,008 KB
6.in AC 4 ms
3,008 KB
7.in AC 3 ms
3,008 KB
8.in AC 3 ms
3,012 KB
9.in AC 3 ms
3,012 KB
A.in AC 4 ms
3,008 KB
B.in AC 2 ms
3,008 KB
C.in AC 2 ms
3,008 KB
D.in AC 3 ms
3,012 KB
E.in AC 3 ms
3,008 KB
F.in AC 2 ms
3,012 KB
G.in AC 4 ms
3,012 KB
system_test1.txt AC 3 ms
3,012 KB
system_test2.txt AC 2 ms
3,012 KB
system_test3.txt AC 4 ms
3,012 KB
system_test4.txt AC 4 ms
3,012 KB
system_test5.txt AC 3 ms
3,012 KB
テストケース一括ダウンロード

ソースコード

diff #
#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