結果

問題 No.186 中華風 (Easy)
ユーザー Shibaken28Shibaken28
提出日時 2023-11-13 16:12:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,589 bytes
コンパイル時間 711 ms
コンパイル使用メモリ 74,112 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-26 03:18:59
合計ジャッジ時間 1,381 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 1 ms
5,376 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "Math/Number-Theory/CRT.test.cpp"
# define PROBLEM "https://yukicoder.me/problems/447"
# include <iostream>
#line 1 "Math/Number-Theory/CRT.hpp"
# include <vector>
# include <utility>
#line 1 "Math/Number-Theory/ext-euclid.hpp"
// 拡張Euclidの互除法
// ax + by = gcd(a, b) となるような (x, y) を求める 
long extGCD(long a, long b, long &x, long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

#line 4 "Math/Number-Theory/CRT.hpp"
using namespace std;

long mod(long a,long m){
    if(a>=0)return a%m; 
    return (m-(-a)%m)%m;
}

/*
中国剰余定理
*/
bool CRT(long b1, long m1, long b2, long m2,long &r,long &m) {
    long p, q;
    long d = extGCD(m1, m2, p, q);
    if ((b2 - b1) % d != 0) return false;
    m = m1 * (m2/d); 
    long tmp = (b2 - b1) / d * p % (m2/d);
    r = mod(b1 + m1 * tmp, m);
    return true;
}

bool CRT(const vector<pair<long,long>> &X,long &r,long &m) {
    int s = X.size();
    r = X.front().first;
    m = X.front().second;
    bool ok = true;
    for(int i=1;i<s;i++){
        ok = CRT(r,m,X[i].first,X[i].second,r,m);
        if(!ok){
            break;
        }
    }
    return ok;
}

#line 4 "Math/Number-Theory/CRT.test.cpp"
using namespace std;

int main(){
    int N = 3;
    vector<pair<long,long>> X(N);
    for(int i=0;i<N;i++){
        cin >> X[i].first >> X[i].second;
    }
    long r,m;
    bool ok = CRT(X,r,m);
    if(ok){
        cout << r << endl;
    }else{
        cout << -1 << endl;
    }
    return 0;
}
0