結果

問題 No.2207 pCr検査
ユーザー gew1fw
提出日時 2025-06-12 17:59:29
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,847 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 82,056 KB
実行使用メモリ 341,080 KB
最終ジャッジ日時 2025-06-12 18:00:02
合計ジャッジ時間 5,921 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    k = int(sys.stdin.readline())
    original_factors = dict()
    primes = []
    for _ in range(k):
        p, e = map(int, sys.stdin.readline().split())
        original_factors[p] = e
        primes.append(p)
    
    # Check condition A: N is p^1
    if k == 1:
        p = primes[0]
        e = original_factors[p]
        if e == 1:
            print(p, 1)
            return
    
    # Prepare 2N's factors
    two_n_factors = defaultdict(int)
    for p, e in original_factors.items():
        two_n_factors[p] = e
    if 2 in two_n_factors:
        two_n_factors[2] += 1
    else:
        two_n_factors[2] = 1
    
    # Check condition B for each prime in primes
    for p_i in primes:
        if two_n_factors.get(p_i, 0) != 1:
            continue
        
        # Create remaining factors after removing one p_i
        remaining_factors = defaultdict(int)
        for p, e in two_n_factors.items():
            if p == p_i:
                if e - 1 > 0:
                    remaining_factors[p] = e - 1
            else:
                remaining_factors[p] = e
        
        # Calculate product of remaining factors
        product = 1
        target = p_i - 1
        overflow = False
        # Process primes in sorted order to minimize computation
        for prime in sorted(remaining_factors.keys()):
            exp = remaining_factors[prime]
            for _ in range(exp):
                product *= prime
                if product > target:
                    overflow = True
                    break
            if overflow:
                break
        if overflow:
            continue
        if product == target:
            print(p_i, 2)
            return
    
    # If no solution found
    print(-1, -1)

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