結果
| 問題 |
No.2207 pCr検査
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:59:25 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,095 bytes |
| コンパイル時間 | 133 ms |
| コンパイル使用メモリ | 82,288 KB |
| 実行使用メモリ | 391,516 KB |
| 最終ジャッジ日時 | 2025-05-14 13:00:44 |
| 合計ジャッジ時間 | 5,668 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | TLE * 1 -- * 29 |
ソースコード
import sys
# Function to compute a^b using binary exponentiation.
# This function supports potentially very large results using Python's arbitrary precision integers.
def fast_pow(base, power):
"""
Calculates base^power efficiently using binary exponentiation.
Handles large integers.
"""
result = 1
# Using Python's built-in pow() might be faster for large integers,
# but this custom implementation clearly shows the algorithm.
# For very large exponents, pow(base, power) is generally preferred.
# Let's stick to the standard binary exponentiation implementation:
while power > 0:
if power % 2 == 1:
result *= base
base *= base
power //= 2
return result
def solve():
"""
Main function to solve the problem. Reads input, checks conditions, searches for (p, r), and prints the result.
"""
# Read the number of distinct prime factors k
k = int(sys.stdin.readline())
# Store the prime factorization of N: list of dictionaries {'p': prime, 'e': exponent}
factors = []
for _ in range(k):
line = sys.stdin.readline().split()
p_val = int(line[0])
e_val = int(line[1])
factors.append({'p': p_val, 'e': e_val})
# The problem statement guarantees p1 < ... < pk, so the factors are already sorted by prime base 'p'.
# Handle the simple case: N is a prime number.
# This occurs if k=1 and the exponent e1=1.
# In this case, N=p1, and we can choose p=p1 and r=1 (since C(p1, 1) = p1).
# Also C(p1, p1-1) = p1 works, but we only need one solution.
if k == 1 and factors[0]['e'] == 1:
print(f"{factors[0]['p']} 1")
return
# Now consider the case where N = C(p, r) for r >= 2 and r <= p-2.
# From number theoretic properties of binomial coefficients C(p, r) where p is prime:
# 1. p must divide C(p, r) for 1 <= r <= p-1. Thus, p must be one of the prime factors of N.
# 2. The exponent of p in the prime factorization of C(p, r) is exactly 1 for 1 <= r <= p-1.
# So, if N = C(p, r), the exponent of p in N must be 1.
# 3. A less trivial property derived using Kummer's Theorem implies that p must be greater than or equal to
# all prime factors of N. If p < p_l for some prime factor p_l of N, then the exponent of p_l
# in C(p, r) would be 0, which contradicts the input N having p_l as a factor.
# Combining these: if a solution exists with r in [2, p-2], then p must be the largest prime factor of N,
# let's call it p_k, and its exponent e_k must be exactly 1.
# Get the largest prime factor pk and its exponent ek.
pk = factors[-1]['p']
ek = factors[-1]['e']
# Check the necessary condition: the exponent ek must be 1.
if ek != 1:
# If N is not prime (already checked) and ek != 1, no solution exists for r >= 2.
# Therefore, no solution overall.
print("-1 -1")
return
# If ek = 1, the only possible candidate for the prime p is pk.
p = pk
# We need to check if there exists an r such that N = C(p, r).
# Using the identity C(p, r) = (p/r) * C(p-1, r-1), and N = p * M where M = N/p,
# we get pM = (p/r) * C(p-1, r-1).
# Dividing by p (since p is prime >= 5, p != 0), we get M = (1/r) * C(p-1, r-1).
# Rearranging gives r * M = C(p-1, r-1).
# Let s = r-1. Then r = s+1. The equation becomes (s+1) * M = C(p-1, s).
# We need to search for an integer s in the range [1, floor((p-1)/2)].
# The range for r is [2, p-2]. Since C(p, r) = C(p, p-r), we only need to check r up to floor(p/2).
# This corresponds to s = r-1 up to floor(p/2) - 1. If p is odd, floor(p/2) = (p-1)/2. Max s is (p-1)/2 - 1 = (p-3)/2.
# Wait, if r = (p-1)/2, s = (p-3)/2. If r = floor(p/2)=(p-1)/2, then s = (p-1)/2 - 1 = (p-3)/2.
# What about r = (p+1)/2? Then s = (p-1)/2. The symmetry point for C(p-1, s) is (p-1)/2.
# We need to check s up to floor((p-1)/2).
# Compute M = N / p using arbitrary precision integers.
M = 1
for i in range(k):
curr_p = factors[i]['p']
curr_e = factors[i]['e']
if curr_p == p:
# Skip the factor p=pk since its exponent in M is e_k - 1 = 1 - 1 = 0.
continue
# Compute curr_p ^ curr_e using fast exponentiation. Handles large numbers.
term = fast_pow(curr_p, curr_e)
M *= term
# Set the upper limit for s search. Due to symmetry C(X, s) = C(X, X-s), we only need check up to X/2.
limit_s = (p - 1) // 2
# Initialize variables for the iterative computation of C(p-1, s).
current_C = 1 # Represents C(p-1, 0)
found_solution = False
for s in range(1, limit_s + 1):
# Calculate C(p-1, s) = C(p-1, s-1) * (p-s) / s iteratively.
# This calculation must be done using integer arithmetic that supports large numbers.
numerator = current_C * (p - s)
# Division is guaranteed to be exact for binomial coefficients.
# Python's // operator performs integer division.
current_C = numerator // s
# Calculate the target value: (s+1) * M.
required_val = (s + 1) * M
# Check if the computed C(p-1, s) matches the target value.
if required_val == current_C:
# Solution found: p=pk, r=s+1.
print(f"{p} {s+1}")
found_solution = True
break # Exit the loop once a solution is found.
# Optimization: Early exit if C(p-1, s) exceeds the required value.
# C(p-1, s) increases monotonically for s in the range [1, floor((p-1)/2)].
# (s+1)M increases linearly.
# If C(p-1, s) becomes greater than (s+1)M, it will never become equal for larger s in this range.
if current_C > required_val:
# No solution possible for this p.
break # Exit the loop.
# If the loop completes without finding a solution.
if not found_solution:
print("-1 -1")
# Execute the main solve function
solve()