結果

問題 No.2207 pCr検査
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:02:22
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,715 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,424 KB
実行使用メモリ 174,356 KB
最終ジャッジ日時 2025-06-12 18:02:36
合計ジャッジ時間 12,158 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

def factorize(n):
    factors = {}
    while n % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        n = n // 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors[i] = factors.get(i, 0) + 1
            n = n // i
        i += 2
    if n > 1:
        factors[n] = 1
    return factors

def factorial_factors(r):
    factors = {}
    for i in range(2, r + 1):
        current = i
        temp = {}
        while current % 2 == 0:
            temp[2] = temp.get(2, 0) + 1
            current = current // 2
        j = 3
        while j * j <= current:
            while current % j == 0:
                temp[j] = temp.get(j, 0) + 1
                current = current // j
            j += 2
        if current > 1:
            temp[current] = 1
        for prime, exp in temp.items():
            factors[prime] = factors.get(prime, 0) + exp
    return factors

# Read input
k = int(input())
prime_factors = {}
for _ in range(k):
    p, e = map(int, input().split())
    prime_factors[p] = e

# Get the largest prime p
if not prime_factors:
    print(-1, -1)
    exit()
p_list = sorted(prime_factors.keys())
p = p_list[-1]

# Check if p's exponent is 1
if prime_factors[p] != 1:
    print(-1, -1)
    exit()

# Compute M's factors
m_factors = prime_factors.copy()
m_factors[p] -= 1
if m_factors[p] == 0:
    del m_factors[p]

# Check for r from 2 to a reasonable upper limit
found = False
for r in range(2, 50):
    if p < r:
        continue  # Skip if p < r since binomial(p, r) would be 0
    
    # Calculate numerator factors: product of (p-1)(p-2)...(p-r+1)
    numerator_factors = {}
    valid_numerator = True
    for num in range(p-1, p - r, -1):
        if num <= 0:
            valid_numerator = False
            break
        factors = factorize(num)
        for prime, exp in factors.items():
            numerator_factors[prime] = numerator_factors.get(prime, 0) + exp
    if not valid_numerator:
        continue
    
    # Calculate denominator factors: r!
    denominator_factors = factorial_factors(r)
    
    # Check if denominator factors are subset of numerator factors
    v_factors = numerator_factors.copy()
    valid = True
    for prime, exp in denominator_factors.items():
        if v_factors.get(prime, 0) < exp:
            valid = False
            break
        v_factors[prime] -= exp
        if v_factors[prime] == 0:
            del v_factors[prime]
    if not valid:
        continue
    
    # Check if v_factors matches m_factors
    if v_factors == m_factors:
        print(p, r)
        found = True
        break

if not found:
    # Check r=1 case (M must be empty)
    if not m_factors:
        print(p, 1)
    else:
        print(-1, -1)
0