結果

問題 No.2119 一般化百五減算
コンテスト
ユーザー Jikky1618
提出日時 2024-04-07 04:28:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,086 bytes
コンパイル時間 2,699 ms
コンパイル使用メモリ 248,688 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-01 04:22:37
合計ジャッジ時間 3,444 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include <debug_print.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif

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

// x ≡ r[i] (mod m[i]) を解き, x ≡ r0 (mod. m0) となる (r0, m0) を返す
// m0 := lcm(m[0], m[1], ...)
pair<ll, ll> crt(const vector<ll>& r, const vector<ll>& m) {
    assert(r.size() == m.size());
    int n = r.size();
    ll r0 = 0, m0 = 1;
    for(int i = 0; i < n; i++){
        assert(1 <= m[i]);
        ll r1 = (r[i] % m[i] + m[i]) % m[i], m1 = m[i], g = gcd(m0, m1);
        // p * m0 + q * m1 = g となる (p, q) を求める
        // このとき p は p * m0 / g ≡ 1 (mod. m1 / g) を満たす
        auto [p, q] = extgcd(m0, m1);
        // r1 ≡ r0 (mod. g) でない場合は解なし
        if((r1 - r0) % g != 0) return {-1, 0};
        // s = (r1 - r0) / g として両辺に s を掛けて
        // p * m0 * s + q * m1 * s = r1 - r0 とする
        // x = r0 + m0 * p * s (= r1 - m1 * p * s) とすると
        // x ≡ r1 (mod. m1), x ≡ r0 (mod. m0) を満たす
        ll u1 = m1 / g;
        ll x = (r1 - r0) / g % u1 * p % u1;
        r0 += m0 * x;
        m0 *= u1; // lcm(m0, m1) = m0 * m1 / g
    }
    r0 = (r0 % m0 + m0) % m0;
    return {r0, m0};
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N, M;
    cin >> N >> M;
    vector<ll> B(M), C(M);
    for(int i = 0; i < M; i++) cin >> B[i] >> C[i], C[i] = (C[i] % B[i] + B[i]) % B[i];

    auto [r, m] = crt(C, B);
    if(r == -1 || r > N) {
        cout << "NaN" << endl;
    }else{
        for(int i = 0; i < M; i++){
            if(r % B[i] != C[i]){
                cout << "NaN" << endl;
                return 0;
            }
        }
        cout << r << endl;
    }


}
0