結果

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

ソースコード

diff # 

from collections import defaultdict

def factorize(n):
    factors = defaultdict(int)
    while n % 2 == 0:
        factors[2] += 1
        n = n // 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors[i] += 1
            n = n // i
        i += 2
    if n > 1:
        factors[n] += 1
    return factors

def main():
    k = int(input())
    factors = {}
    for _ in range(k):
        p, e = map(int, input().split())
        factors[p] = e

    if not factors:
        print(-1, -1)
        return

    p_max = max(factors.keys())
    if factors[p_max] != 1:
        print(-1, -1)
        return

    # Check if N is just p_max
    if len(factors) == 1 and factors[p_max] == 1:
        print(p_max, 1)
        return

    # Check for r=2 case
    two_n_factors = defaultdict(int, {key: val for key, val in factors.items()})
    two_n_factors[2] += 1
    two_n_factors[p_max] -= 1
    if two_n_factors[p_max] == 0:
        del two_n_factors[p_max]
    two_n_factors = dict(two_n_factors)

    pm1 = p_max - 1
    pm1_factors = factorize(pm1)
    pm1_factors = dict(pm1_factors)
    if pm1_factors == two_n_factors:
        print(p_max, 2)
        return

    # Check for r=3 case
    six_n_factors = defaultdict(int, {key: val for key, val in factors.items()})
    six_n_factors[2] += 1
    six_n_factors[3] += 1
    six_n_factors[p_max] -= 1
    if six_n_factors[p_max] == 0:
        del six_n_factors[p_max]
    six_n_factors = dict(six_n_factors)

    pm1 = p_max - 1
    pm2 = p_max - 2
    pm1_factors = factorize(pm1)
    pm2_factors = factorize(pm2)
    combined = defaultdict(int)
    for p, e in pm1_factors.items():
        combined[p] += e
    for p, e in pm2_factors.items():
        combined[p] += e
    combined = dict(combined)

    if combined == six_n_factors:
        print(p_max, 3)
        return

    print(-1, -1)

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