結果

問題 No.2119 一般化百五減算
コンテスト
ユーザー cubinglover
提出日時 2022-11-04 22:43:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,894 bytes
コンパイル時間 1,961 ms
コンパイル使用メモリ 198,560 KB
最終ジャッジ日時 2025-02-08 18:08:56
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define repl(i, l, r) for (int i = (l); i < (int)(r); ++i)
#define rep(i, n) repl(i, 0, n)
#define CST(x) cout << fixed << setprecision(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using ll = long long;
constexpr ll MOD = 998244353;
constexpr int inf = 1e9 + 10;
constexpr ll INF = (ll)4e18 + 10;
constexpr int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
constexpr int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
const double PI = acos(-1);
template <typename T>
using MaxHeap = priority_queue<T>;
template <typename T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
inline bool chmax(T &a, T b) {
    return ((a < b) ? (a = b, true) : (false));
}
template <typename T>
inline bool chmin(T &a, T b) {
    return ((a > b) ? (a = b, true) : (false));
}
template <typename T>
inline void yn(const T &a) {
    ((a) ? (cout << "Yes" << endl) : (cout << "No" << endl));
}
template <typename T>
inline void YN(const T &a) {
    ((a) ? (cout << "YES" << endl) : (cout << "NO" << endl));
}
constexpr long long safe_mod(long long x, long long m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
    a = safe_mod(a, b);
    if (a == 0) return {b, 0};
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;
    while (t) {
        long long 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<long long, long long> crt(const std::vector<long long> &r,
                                    const std::vector<long long> &m) {
    assert(r.size() == m.size());
    int n = int(r.size());
    long long r0 = 0, m0 = 1;
    for (int i = 0; i < n; i++) {
        assert(1 <= m[i]);
        long long r1 = safe_mod(r[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;
        }
        long long g, im;
        std::tie(g, im) = inv_gcd(m0, m1);

        long long 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};
}
int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    vector<ll> a(m), b(m);
    rep(i, m) cin >> a[i] >> b[i];

    rep(i, m) b[i] = (b[i] % a[i] + a[i]) % a[i];

    pair<ll, ll> ans = crt(b, a);

    if (ans.second == 0 or ans.first <= n) {
        cout << "NaN" << endl;
    } else {
        cout << ans.first << endl;
    }


    return 0;
}
0