結果

問題 No.2207 pCr検査
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:07:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,530 bytes
コンパイル時間 698 ms
コンパイル使用メモリ 81,300 KB
実行使用メモリ 53,688 KB
最終ジャッジ日時 2025-04-16 16:14:55
合計ジャッジ時間 6,238 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

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 main():
    input = sys.stdin.read().split()
    idx = 0
    k = int(input[idx])
    idx += 1
    factors = {}
    for _ in range(k):
        p = int(input[idx])
        e = int(input[idx+1])
        factors[p] = e
        idx += 2
    
    # Check if N is a prime (k=1 and e=1)
    if len(factors) == 1:
        p, e = next(iter(factors.items()))
        if e == 1:
            print(p, 1)
            return
    
    # Check for r=2 case
    for p in list(factors.keys()):
        if factors[p] != 1:
            continue
        
        # Create expected factors
        expected = factors.copy()
        expected[p] -= 1
        if expected[p] == 0:
            del expected[p]
        # Add 2
        if 2 in expected:
            expected[2] += 1
        else:
            expected[2] = 1
        
        # Compute p-1
        target = p - 1
        if target <= 1:
            continue
        
        # Factorize target
        actual = factorize(target)
        
        # Compare actual and expected
        if actual == expected and p >= 5:
            print(p, 2)
            return
    
    # No solution found
    print(-1, -1)

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