結果

問題 No.2207 pCr検査
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:19:49
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,003 bytes
コンパイル時間 288 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 315,944 KB
最終ジャッジ日時 2025-03-20 20:20:39
合計ジャッジ時間 7,355 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from math import isqrt

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()
    ptr = 0
    k = int(input[ptr])
    ptr += 1
    n_factors = {}
    for _ in range(k):
        p = int(input[ptr])
        e = int(input[ptr+1])
        ptr += 2
        n_factors[p] = e

    # Check if N is a single prime (r=1 case)
    if len(n_factors) == 1:
        p = next(iter(n_factors))
        if n_factors[p] == 1:
            print(p, 1)
            return

    # Collect candidates (primes with exponent 1)
    candidates = [p for p, e in n_factors.items() if e == 1]

    # Check each candidate for r=2 case
    for p in candidates:
        # For p=2, check if N == 2
        if p == 2:
            if len(n_factors) == 1 and n_factors.get(2, 0) == 1:
                print(2, 1)
                return
            continue

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

        # r=2 case: check if (p-1)/2 == M
        # compute factors of p-1 divided by 2
        p_minus_1 = p - 1
        pm1_factors = factorize(p_minus_1)
        # check if divisible by 2
        if 2 not in pm1_factors:
            continue  # (p-1) is odd, can't divide by 2
        # divide by 2
        pm1_factors[2] -= 1
        if pm1_factors[2] == 0:
            del pm1_factors[2]
        required_factors = pm1_factors

        # compare with m_factors
        if required_factors == m_factors:
            print(p, 2)
            return

    # Check other rs here if needed, but omitted for brevity

    # If no solution found
    print(-1, -1)

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