結果

問題 No.3022 一元一次式 mod 1000000000
コンテスト
ユーザー t98slider
提出日時 2025-02-14 21:53:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,823 bytes
コンパイル時間 2,013 ms
コンパイル使用メモリ 199,572 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-14 21:55:02
合計ジャッジ時間 3,070 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

/*__int128 inv_mod(__int128 x, __int128 m) {
    assert(1 <= m);
    auto z = inv_gcd(x, m);
    assert(z.first == 1);
    return z.second;
}*/

constexpr std::pair<__int128, __int128> inv_gcd(__int128 a, __int128 b) {
    a = (a % b + b) % b;
    if (a == 0) return {b, 0};
    __int128 s = b, t = a;
    __int128 m0 = 0, m1 = 1;

    while (t) {
        __int128 u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

std::pair<__int128, __int128> crt(const std::vector<__int128>& r,
                                    const std::vector<__int128>& m) {
    assert(r.size() == m.size());
    int n = int(r.size());
    __int128 r0 = 0, m0 = 1;
    for (int i = 0; i < n; i++) {
        assert(1 <= m[i]);
        __int128 r1 = (r[i] % m[i] + m[i]) % m[i], m1 = m[i];
        if (m0 < m1) {
            std::swap(r0, r1);
            std::swap(m0, m1);
        }
        if (m0 % m1 == 0) {
            if (r0 % m1 != r1) return {0, 0};
            continue;
        }
        __int128 g, im;
        std::tie(g, im) = inv_gcd(m0, m1);
        __int128 u1 = (m1 / g);
        if ((r1 - r0) % g) return {0, 0};
        long long x = (r1 - r0) / g % u1 * im % u1;
        r0 += x * m0;
        m0 *= u1;
        if (r0 < 0) r0 += m0;
    }
    return {r0, m0};
}

void solve(){
    ll n, m;
    cin >> n >> m;
    auto pa = crt({-m, 0}, {1'000'000'000, n});
    if(pa.second == 0) cout << -1 << '\n';
    else cout << (long long)(pa.first / n) << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) solve();
}
0