結果

問題 No.1931 Fraction 2
ユーザー lam6er
提出日時 2025-04-16 15:29:37
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,445 bytes
コンパイル時間 407 ms
コンパイル使用メモリ 81,408 KB
実行使用メモリ 126,720 KB
最終ジャッジ日時 2025-04-16 15:32:16
合計ジャッジ時間 15,422 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from collections import defaultdict

MOD = 998244353

def factorize(n):
    factors = defaultdict(int)
    while n % 2 == 0:
        factors[2] += 1
        n //= 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors[i] += 1
            n //= i
        i += 2
    if n > 1:
        factors[n] += 1
    return factors

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    
    max_factors = defaultdict(int)
    B_list = []
    for _ in range(N):
        A = int(input[ptr])
        B = int(input[ptr+1])
        ptr +=2
        B_list.append(B)
        factors = factorize(B)
        for p, cnt in factors.items():
            if max_factors[p] < cnt:
                max_factors[p] = cnt
    
    # Compute LCM mod MOD
    LCM_mod = 1
    for p, cnt in max_factors.items():
        LCM_mod = (LCM_mod * pow(p, cnt, MOD)) % MOD
    
    sum_part = 0
    for i in range(N):
        B = B_list[i]
        A = int(input[2*i + 1])  # A is the first element of the pair
        inv_B = pow(B, MOD-2, MOD)
        term = (A * LCM_mod) % MOD
        term = (term * inv_B) % MOD
        sum_part = (sum_part + term) % MOD
    
    # Compute GCD of sum_part and LCM_mod
    g = math.gcd(sum_part, LCM_mod)
    inv_g = pow(g, MOD-2, MOD)
    c = (sum_part * inv_g) % MOD
    d = (LCM_mod * inv_g) % MOD
    print(c, d)

if __name__ == "__main__":
    main()
0