結果
| 問題 |
No.1931 Fraction 2
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:09:31 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,986 bytes |
| コンパイル時間 | 392 ms |
| コンパイル使用メモリ | 82,100 KB |
| 実行使用メモリ | 104,616 KB |
| 最終ジャッジ日時 | 2025-05-14 13:10:51 |
| 合計ジャッジ時間 | 9,614 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 10 TLE * 1 -- * 25 |
ソースコード
import sys
import math
# Set higher recursion depth for extended_gcd if needed, though iterative is safer
# sys.setrecursionlimit(2000)
# Function to compute greatest common divisor
def gcd(a, b):
"""Computes the greatest common divisor of a and b."""
while b:
a, b = b, a % b
return a
# Function for Extended Euclidean Algorithm
def extended_gcd(a, b):
"""
Computes extended Euclidean Algorithm.
Returns tuple (d, x, y) such that d = gcd(a, b) and ax + by = d.
"""
if a == 0:
return b, 0, 1
d, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return d, x, y
# Function to compute modular inverse
def modInverse(a, m):
"""
Computes the modular multiplicative inverse of a modulo m.
Raises ValueError if inverse does not exist (i.e., gcd(a, m) != 1).
"""
d, x, y = extended_gcd(a, m)
if d != 1:
raise ValueError(f"Modular inverse does not exist for a={a}, m={m}, gcd={d}")
# Return x mod m, ensuring result is positive
return (x % m + m) % m
# Function for modular exponentiation
def fast_pow(base, power, modulus):
"""
Computes (base^power) % modulus using binary exponentiation.
"""
result = 1
base %= modulus # Ensure base is within modulo range
while power > 0:
if power % 2 == 1:
result = (result * base) % modulus
base = (base * base) % modulus
power //= 2
return result
# --- Sieve and Factorization ---
MAX_VAL = 200001 # Maximum value for A_i, B_i + 1
spf = [i for i in range(MAX_VAL)] # Smallest Prime Factor array
primes = [] # List of primes up to MAX_VAL
def sieve():
"""
Sieve of Eratosthenes to precompute Smallest Prime Factor (SPF) for numbers up to MAX_VAL.
"""
is_prime = [True] * MAX_VAL
is_prime[0] = is_prime[1] = False
for i in range(2, MAX_VAL):
if is_prime[i]:
spf[i] = i
primes.append(i)
# Mark multiples of i as not prime and set their SPF
# Start from i*i to optimize
for multiple in range(i * i, MAX_VAL, i):
if is_prime[multiple]: # Check if SPF hasn't been set yet
is_prime[multiple] = False
spf[multiple] = i
sieve() # Precompute SPF table
def get_prime_factorization(num):
"""
Factorizes a number using the precomputed SPF table.
Returns a dictionary {prime: exponent}.
"""
factors = {}
if num <= 0: return {} # Handle non-positive inputs
if num == 1: return {} # Base case for 1
while num > 1:
p = spf[num]
count = 0
while num > 0 and num % p == 0: # Check divisibility and ensure num remains positive
num //= p
count += 1
if count > 0: # Store the prime factor and its exponent
factors[p] = count
# Optimization: if the remaining number is prime (its SPF is itself)
if num > 1 and spf[num] == num:
factors[num] = factors.get(num, 0) + 1
break # Factorization complete
# Exit loop if num becomes 1
if num == 1: break
return factors
# --- Main Solve Function ---
MOD = 998244353 # The modulus specified in the problem
def solve():
"""
Main logic to solve the fraction sum problem.
"""
N = int(sys.stdin.readline())
A = [] # List of numerators
B = [] # List of denominators
B_factors = [] # List of prime factorizations of denominators
for i in range(N):
line = sys.stdin.readline().split()
ai = int(line[0])
bi = int(line[1])
# Basic validation based on problem constraints
if not (1 <= ai <= 200000): raise ValueError(f"A_i={ai} out of bounds 1..200000")
if not (1 <= bi <= 200000): raise ValueError(f"B_i={bi} out of bounds 1..200000")
A.append(ai)
B.append(bi)
if bi >= MAX_VAL: raise ValueError(f"B_i={bi} exceeds MAX_VAL limit {MAX_VAL-1}")
B_factors.append(get_prime_factorization(bi))
# Compute maximum exponent E_p for each prime p involved in any B_i
max_exponents = {} # {prime: max_exponent}
involved_primes = set() # Set of primes that divide at least one B_i
for factors in B_factors:
for p, exp in factors.items():
involved_primes.add(p)
# Update the maximum exponent seen so far for prime p
if p not in max_exponents or exp > max_exponents[p]:
max_exponents[p] = exp
involved_primes_list = sorted(list(involved_primes)) # Sorted list of primes
K = len(involved_primes_list) # Number of distinct prime factors across all B_i
# Calculate L mod MOD, where L = lcm(B_1, ..., B_N)
L_mod = 1
for p in involved_primes_list:
Ep = max_exponents.get(p, 0)
if Ep > 0: # Only include primes with positive maximum exponent
term = fast_pow(p, Ep, MOD)
L_mod = (L_mod * term) % MOD
# Calculate C mod MOD, where C is the numerator of the sum before reduction
# C = sum(A_i * (L / B_i))
# We compute (L/B_i) mod MOD as (L mod MOD) * (B_i^{-1} mod MOD) mod MOD
C_mod = 0
for i in range(N):
if B[i] == 0: continue # Should not happen based on constraints
# B_i^{-1} mod MOD exists because B_i <= 200000 < MOD and MOD is prime
Bi_inv_mod = fast_pow(B[i], MOD - 2, MOD) # Using Fermat's Little Theorem for prime MOD
term = (A[i] * L_mod) % MOD
term = (term * Bi_inv_mod) % MOD
C_mod = (C_mod + term) % MOD
# Compute G = gcd(C, L). We need its prime factorization G = product(p^gp)
G_mod = 1 # G mod MOD
G_factors = {} # Stores {prime: exponent gp} for G
# For each prime p involved, compute gp = min(Ep, nu_p(C))
# where nu_p(C) is the exponent of p in the prime factorization of C.
for p_idx, p in enumerate(involved_primes_list):
Ep = max_exponents[p] # Maximum exponent of p in any B_i
# Compute C mod p^(Ep+1) to determine nu_p(C) up to Ep
Mp_val = pow(p, Ep + 1) # Exact value of p^(Ep+1)
# Compute L'_p = L / p^Ep = product_{q!=p} q^Eq modulo Mp_val
L_prime_p_mod_Mp = 1
for q_idx, q in enumerate(involved_primes_list):
if q != p:
Eq = max_exponents.get(q, 0)
if Eq > 0:
term = fast_pow(q, Eq, Mp_val)
L_prime_p_mod_Mp = (L_prime_p_mod_Mp * term) % Mp_val
# Calculate C mod Mp_val
C_mod_Mp = 0
for i in range(N):
Bi_p_part_exp = B_factors[i].get(p, 0) # Exponent of p in B_i
# Calculate B'_ip = B[i] / p^e_ip. This is the part of B_i coprime to p.
p_pow_Bi_p_part_exp = pow(p, Bi_p_part_exp)
if B[i] == 0: continue
if p_pow_Bi_p_part_exp == 0: raise ValueError("p^exp resulted in 0") # Impossible for p>=2
B_prime_ip_val = B[i] // p_pow_Bi_p_part_exp
if B_prime_ip_val == 0: continue # Should only happen if B[i]=0 initially
# Calculate (L/B_i) mod Mp_val = (p^(Ep - e_ip) * Z_ip) mod Mp_val
# where Z_ip = L'_p / B'_ip
B_prime_ip_mod_Mp = B_prime_ip_val % Mp_val
if B_prime_ip_mod_Mp == 0:
# This implies gcd(B'_ip, Mp) = Mp != 1. But gcd(B'_ip, p)=1, so gcd(B'_ip, Mp)=1.
# This case should be impossible. Included for robustness / debugging.
raise ValueError(f"Impossible case: B_prime_ip_mod_Mp == 0 for i={i}, p={p}")
# B'_ip is coprime to Mp=p^(Ep+1), so inverse exists
B_prime_ip_inv_mod_Mp = modInverse(B_prime_ip_mod_Mp, Mp_val)
# Z_ip mod Mp = (L'_p mod Mp) * (B'_ip^{-1} mod Mp) mod Mp
Z_ip_mod_Mp = (L_prime_p_mod_Mp * B_prime_ip_inv_mod_Mp) % Mp_val
# Calculate p^(Ep - e_ip) mod Mp
p_power_term = fast_pow(p, Ep - Bi_p_part_exp, Mp_val)
# Calculate A_i * (L/B_i) mod Mp
Ai_mod_Mp = A[i] % Mp_val # Ensure A[i] is taken mod Mp
term_i = (Ai_mod_Mp * p_power_term) % Mp_val
term_i = (term_i * Z_ip_mod_Mp) % Mp_val
C_mod_Mp = (C_mod_Mp + term_i) % Mp_val
# Determine nu_p(C) based on C_mod_Mp
if C_mod_Mp == 0:
# If C = 0 mod p^(Ep+1), then nu_p(C) >= Ep+1
nu_p_C = Ep + 1
else:
# Calculate the exact exponent of p dividing C_mod_Mp
temp_C = C_mod_Mp
nu_p_C = 0
# Keep dividing by p until it's no longer divisible
while temp_C > 0 and temp_C % p == 0:
temp_C //= p
nu_p_C += 1
# gp = min(exponent of p in L, exponent of p in C)
gp = min(Ep, nu_p_C)
G_factors[p] = gp # Store the exponent of p in G
# Accumulate G mod MOD
if gp > 0:
G_mod = (G_mod * fast_pow(p, gp, MOD)) % MOD
# Final computation of c and d modulo MOD
# c = (C / G) mod MOD = (C mod MOD) * (G^{-1} mod MOD) mod MOD
# d = (L / G) mod MOD = product(p^(Ep - gp)) mod MOD
if G_mod == 0:
# G mod MOD = 0 impossible since MOD is prime > max(p)
pass
# G^{-1} mod MOD exists since G is not a multiple of MOD
G_inv_mod = fast_pow(G_mod, MOD - 2, MOD)
final_c = (C_mod * G_inv_mod) % MOD
# Calculate d = L/G mod MOD
final_d = 1
for p in involved_primes_list:
Ep = max_exponents.get(p, 0)
gp = G_factors.get(p, 0)
exp_diff = Ep - gp # Exponent of p in d
if exp_diff > 0:
term = fast_pow(p, exp_diff, MOD)
final_d = (final_d * term) % MOD
# Output the result
print(final_c, final_d)
# --- Execution ---
solve()