結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー tubo28
提出日時 2015-10-23 21:05:34
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,543 bytes
コンパイル時間 391 ms
コンパイル使用メモリ 57,036 KB
最終ジャッジ日時 2024-11-14 19:20:35
合計ジャッジ時間 791 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:39:19: error: ‘std::pair<__int128, __int128> crt’ redeclared as different kind of entity
   39 | pair<lll,lll> crt(vector<lll> a, vector<lll> m){
      |                   ^~~~~~
main.cpp:12:15: note: previous declaration ‘std::pair<__int128, __int128> crt(lll, lll, lll, lll)’
   12 | pair<lll,lll> crt(lll a1, lll m1, lll a2, lll m2){
      |               ^~~
main.cpp:39:19: error: ‘vector’ was not declared in this scope
   39 | pair<lll,lll> crt(vector<lll> a, vector<lll> m){
      |                   ^~~~~~
main.cpp:6:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    5 | #include <algorithm>
  +++ |+#include <vector>
    6 | using namespace std;
main.cpp:39:29: error: expected primary-expression before ‘>’ token
   39 | pair<lll,lll> crt(vector<lll> a, vector<lll> m){
      |                             ^
main.cpp:39:31: error: ‘a’ was not declared in this scope
   39 | pair<lll,lll> crt(vector<lll> a, vector<lll> m){
      |                               ^
main.cpp:39:34: error: ‘vector’ was not declared in this scope
   39 | pair<lll,lll> crt(vector<lll> a, vector<lll> m){
      |                                  ^~~~~~
main.cpp:39:34: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
main.cpp:39:44: error: expected primary-expression before ‘>’ token
   39 | pair<lll,lll> crt(vector<lll> a, vector<lll> m){
      |                                            ^
main.cpp:39:46: error: ‘m’ was not declared in this scope; did you mean ‘tm’?
   39 | pair<lll,lll> crt(vector<lll> a, vector<lll> m){
      |                                              ^
      |                                              tm
main.cpp: In function ‘int main()’:
main.cpp:52:9: error: ‘vector’ was not declared in this scope
   52 |         vector<lll> x(n), y(n);
      |         ^~~~~~
main.cpp:52:9: note: ‘std::vector’

ソースコード

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