結果

問題 No.1931 Fraction 2
ユーザー lam6er
提出日時 2025-04-15 21:28:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,008 bytes
コンパイル時間 301 ms
コンパイル使用メモリ 81,416 KB
実行使用メモリ 79,636 KB
最終ジャッジ日時 2025-04-15 21:31:54
合計ジャッジ時間 6,367 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 10 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    A = []
    B = []
    from collections import defaultdict

    max_prime = 2 * 10**5
    spf = list(range(max_prime + 1))
    for i in range(2, int(max_prime**0.5) + 1):
        if spf[i] == i:
            for j in range(i*i, max_prime + 1, i):
                if spf[j] == j:
                    spf[j] = i

    def factorize(x):
        factors = defaultdict(int)
        while x > 1:
            p = spf[x]
            while x % p == 0:
                factors[p] += 1
                x //= p
        return factors

    lcm_factors = defaultdict(int)
    B_factors_list = []
    for _ in range(N):
        a = int(input[idx])
        b = int(input[idx + 1])
        A.append(a)
        B.append(b)
        idx += 2
        factors = factorize(b)
        B_factors_list.append(factors)
        for p, cnt in factors.items():
            if lcm_factors[p] < cnt:
                lcm_factors[p] = cnt

    primes = list(lcm_factors.keys())

    sum_total = 0
    LCM_mod = 1
    for p in primes:
        LCM_mod = LCM_mod * pow(p, lcm_factors[p], MOD) % MOD

    g = 1
    for p in primes:
        e_L = lcm_factors[p]
        e_S = 0
        current_k = e_L
        found = False
        while current_k > 0:
            sum_mod_pk = 0
            for i in range(N):
                a = A[i]
                b_factors = B_factors_list[i]
                if p in b_factors:
                    e_Bi = b_factors[p]
                    exponent_p_Mi = e_L - e_Bi
                    if exponent_p_Mi >= current_k:
                        term = 0
                    else:
                        pk = pow(p, current_k)
                        Mi_part = 1
                        for q in b_factors:
                            if q == p:
                                continue
                            Mi_part = Mi_part * pow(q, lcm_factors[q] - b_factors[q], pk) % pk
                        for q in primes:
                            if q == p or q in b_factors:
                                continue
                            Mi_part = Mi_part * pow(q, lcm_factors[q], pk) % pk
                        Mi_part = Mi_part * pow(p, exponent_p_Mi, pk) % pk
                        term = (a % pk) * Mi_part % pk
                else:
                    exponent_p_Mi = e_L
                    if exponent_p_Mi >= current_k:
                        term = 0
                    else:
                        pk = pow(p, current_k)
                        Mi_part = 1
                        for q in b_factors_list[i]:
                            Mi_part = Mi_part * pow(q, lcm_factors[q] - b_factors_list[i][q], pk) % pk
                        for q in primes:
                            if q == p or q in b_factors_list[i]:
                                continue
                            Mi_part = Mi_part * pow(q, lcm_factors[q], pk) % pk
                        Mi_part = Mi_part * pow(p, exponent_p_Mi, pk) % pk
                        term = (a % pk) * Mi_part % pk
                sum_mod_pk = (sum_mod_pk + term) % pk
            if sum_mod_pk == 0:
                e_S = current_k
                found = True
                break
            current_k -= 1
        if not found:
            e_S = 0
        g *= pow(p, min(e_L, e_S))
    
    g_mod = g % MOD
    if g_mod == 0:
        c_mod = 0
        d_mod = 0
    else:
        sum_mod = 0
        LCM_mod = 1
        for p in primes:
            LCM_mod = LCM_mod * pow(p, lcm_factors[p], g * MOD) % (g * MOD)
        for i in range(N):
            a = A[i]
            b = B[i]
            Mi = (LCM_mod // b) % (g * MOD)
            term = (a % (g * MOD)) * Mi % (g * MOD)
            sum_mod = (sum_mod + term) % (g * MOD)
        c = (sum_mod // g) % MOD
        d = (LCM_mod // g) % MOD
        c_mod = c
        d_mod = d
    print(c_mod, d_mod)

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