結果

問題 No.1931 Fraction 2
コンテスト
ユーザー limbo
提出日時 2025-05-22 23:46:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,785 bytes
コンパイル時間 2,559 ms
コンパイル使用メモリ 209,148 KB
実行使用メモリ 190,496 KB
最終ジャッジ日時 2025-05-22 23:46:48
合計ジャッジ時間 8,271 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 6 WA * 4 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int MAXN = 200005;

// Modular exponentiation
ll modpow(ll a, ll b, ll mod = MOD) {
    ll res = 1;
    a %= mod;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

// Modular inverse (Fermat's little theorem)
ll modinv(ll a, ll mod = MOD) {
    return modpow(a, mod - 2, mod);
}

// Sieve for smallest prime factors
vector<int> smallest_prime_factor(int n) {
    vector<int> spf(n+1);
    iota(spf.begin(), spf.end(), 0);
    for(int i = 2; i * i <= n; ++i) {
        if(spf[i] == i) {
            for(int j = i*i; j <= n; j += i) {
                if(spf[j] == j) spf[j] = i;
            }
        }
    }
    return spf;
}

// Factorization using SPF
map<int, int> factorize(int x, const vector<int>& spf) {
    map<int, int> res;
    while(x > 1) {
        int p = spf[x];
        res[p]++;
        x /= p;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N), B(N);
    int maxB = 0;
    for(int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i];
        maxB = max(maxB, B[i]);
    }

    // Precompute smallest prime factors
    auto spf = smallest_prime_factor(maxB);

    // For each prime, store the maximum exponent in any B_i
    map<int, int> max_exp;
    vector<map<int, int>> B_factors(N);
    for(int i = 0; i < N; ++i) {
        B_factors[i] = factorize(B[i], spf);
        for(auto [p, e] : B_factors[i]) {
            max_exp[p] = max(max_exp[p], e);
        }
    }

    // For each prime, compute how many times it divides the numerator sum
    map<int, int> reduce_exp;
    for(auto [p, m_p] : max_exp) {
        ll modp = 1;
        for(int i = 0; i < m_p; ++i) modp *= p;
        ll sum = 0;
        for(int i = 0; i < N; ++i) {
            int e = B_factors[i][p];
            ll coef = 1;
            for(int j = 0; j < m_p - e; ++j) coef *= p;
            ll denom = B[i];
            for(int j = 0; j < e; ++j) denom /= p;
            ll inv = modinv(denom, modp);
            sum = (sum + A[i] * coef % modp * inv % modp) % modp;
        }
        int k_p = 0;
        ll tmp = sum;
        while(tmp % p == 0 && k_p < m_p && tmp != 0) {
            tmp /= p;
            k_p++;
        }
        reduce_exp[p] = m_p - k_p;
    }

    // Build the denominator
    ll d = 1;
    for(auto [p, e] : reduce_exp) {
        for(int i = 0; i < e; ++i) d = d * p % MOD;
    }

    // Compute the sum of fractions modulo MOD
    ll c = 0;
    for(int i = 0; i < N; ++i) {
        c = (c + 1LL * A[i] * modinv(B[i]) % MOD) % MOD;
    }
    c = c * d % MOD;

    cout << c << " " << d << endl;
    return 0;
}
0