結果

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

ソースコード

diff # 

import sys
import math
MOD = 998244353

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    A = []
    B = []
    max_b = 0
    for _ in range(N):
        a, b = map(int, sys.stdin.readline().split())
        A.append(a)
        B.append(b)
        if b > max_b:
            max_b = b

    # Precompute smallest prime factors up to max_b
    SPF = [0] * (max_b + 1)
    for i in range(2, max_b + 1):
        if SPF[i] == 0:
            SPF[i] = i
            for j in range(i*i, max_b+1, i):
                if SPF[j] == 0:
                    SPF[j] = i

    # Factorize each B_i and track max exponents
    from collections import defaultdict
    prime_max = defaultdict(int)
    factorizations = []
    for b in B:
        factors = {}
        if b == 1:
            factorizations.append(factors)
            continue
        x = b
        while x != 1:
            p = SPF[x]
            cnt = 0
            while x % p == 0:
                cnt += 1
                x //= p
            factors[p] = cnt
            if cnt > prime_max[p]:
                prime_max[p] = cnt
        factorizations.append(factors)

    # Compute LCM_mod
    LCM_mod = 1
    lcm_primes = list(prime_max.keys())
    for p in lcm_primes:
        exp = prime_max[p]
        LCM_mod = LCM_mod * pow(p, exp, MOD) % MOD

    # Compute sum_num_mod
    sum_num_mod = 0
    for i in range(N):
        a = A[i]
        b_factors = factorizations[i]
        m_i_mod = 1
        for p in lcm_primes:
            exp = prime_max[p]
            if p in b_factors:
                e_p = b_factors[p]
                current_exp = exp - e_p
            else:
                current_exp = exp
            m_i_mod = m_i_mod * pow(p, current_exp, MOD) % MOD
        term = a * m_i_mod % MOD
        sum_num_mod = (sum_num_mod + term) % MOD

    # Compute GCD of sum_num_mod and LCM_mod
    g = math.gcd(sum_num_mod, LCM_mod)
    # Compute inverse of g modulo MOD
    inv_g = pow(g, MOD-2, MOD)
    c = sum_num_mod * inv_g % MOD
    d = LCM_mod * inv_g % MOD
    print(c, d)

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