結果

問題 No.1931 Fraction 2
コンテスト
ユーザー limbo
提出日時 2025-05-22 23:12:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,212 bytes
コンパイル時間 1,985 ms
コンパイル使用メモリ 198,712 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-22 23:12:33
合計ジャッジ時間 9,218 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 2 RE * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// Helper to handle modulo for negatives
int mod(int x) {
    x %= MOD;
    if (x < 0) x += MOD;
    return x;
}

// GCD
int gcd(int a, int b) {
    while (b) tie(a, b) = make_pair(b, a % b);
    return a;
}

// Multiply with __int128 and return int64_t result
__int128 mult(__int128 a, __int128 b) {
    return a * b;
}

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

    int n;
    cin >> n;
    vector<int> X(n), Y(n);
    for (int i = 0; i < n; ++i) cin >> X[i] >> Y[i];

    // Compute the product of all Y_i
    __int128 den = 1;
    for (int i = 0; i < n; ++i) {
        den *= Y[i];
    }

    // Compute numerator = sum of X_i * (den / Y_i)
    __int128 num = 0;
    for (int i = 0; i < n; ++i) {
        __int128 mult_term = den / Y[i];
        num += (__int128)X[i] * mult_term;
    }

    // Reduce the final fraction
    int64_t num64 = (int64_t)num;
    int64_t den64 = (int64_t)den;
    int64_t g = gcd(num64, den64);
    num64 /= g;
    den64 /= g;

    // Print the reduced fraction modulo MOD
    cout << mod(num64) << ' ';
    cout << mod(den64) << '\n';
    return 0;
}
0