結果

問題 No.2207 pCr検査
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:56:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,562 bytes
コンパイル時間 274 ms
コンパイル使用メモリ 82,836 KB
実行使用メモリ 340,416 KB
最終ジャッジ日時 2025-03-31 17:57:44
合計ジャッジ時間 6,146 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

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 main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    k = int(input[idx])
    idx +=1
    original_factors = {}
    primes_list = []
    for _ in range(k):
        p = int(input[idx])
        e = int(input[idx+1])
        original_factors[p] = e
        primes_list.append(p)
        idx +=2
    
    candidates = [p for p in primes_list if original_factors[p] == 1]
    
    for p_prime in candidates:
        if p_prime == 2:
            continue
        m = (p_prime - 1) // 2
        m_factors = factorize(m)
        remaining_factors = original_factors.copy()
        del remaining_factors[p_prime]
        
        remaining_keys = set(remaining_factors.keys())
        m_keys = set(m_factors.keys())
        if remaining_keys != m_keys:
            continue
        
        match = True
        for key in remaining_keys:
            if remaining_factors.get(key, 0) != m_factors.get(key, 0):
                match = False
                break
        if not match:
            continue
        
        print(p_prime, 2)
        return
    
    if k == 1 and original_factors[primes_list[0]] == 1:
        print(primes_list[0], 1)
        return
    
    print(-1, -1)

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