結果

問題 No.2207 pCr検査
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:01:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,242 bytes
コンパイル時間 427 ms
コンパイル使用メモリ 81,596 KB
実行使用メモリ 168,624 KB
最終ジャッジ日時 2025-04-15 23:03:02
合計ジャッジ時間 5,900 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    k = int(input[idx])
    idx += 1
    N_factors = {}
    for _ in range(k):
        p = int(input[idx])
        e = int(input[idx + 1])
        N_factors[p] = e
        idx += 2

    # Check for r=1 case: N must be a single prime with exponent 1
    if len(N_factors) == 1:
        p_i, e_i = next(iter(N_factors.items()))
        if e_i == 1:
            print(p_i, 1)
            return

    # Check for each p_i in N's factors
    for p_i in list(N_factors.keys()):
        # Check condition a: exponent of p_i is 1
        if N_factors[p_i] != 1:
            continue
        # Check condition b: all other primes are less than p_i
        valid = True
        for q in N_factors:
            if q >= p_i and q != p_i:
                valid = False
                break
        if not valid:
            continue

        # Check r=2 case
        # Build 2*N factors
        two_n_factors = {}
        for q, exp in N_factors.items():
            two_n_factors[q] = exp
        if 2 in two_n_factors:
            two_n_factors[2] += 1
        else:
            two_n_factors[2] = 1

        # Check if p_i is in two_n_factors with exponent 1
        if p_i not in two_n_factors or two_n_factors[p_i] != 1:
            continue

        # Compute the product of two_n_factors after removing one p_i
        product = 1
        for q, exp in two_n_factors.items():
            if q == p_i:
                if exp - 1 == 0:
                    continue
                product *= q ** (exp - 1)
            else:
                product *= q ** exp
        if product == p_i - 1:
            print(p_i, 2)
            return

    # Check r=2 case where p_i is in two_n_factors but not in N_factors (unlikely but possible?)
    # Build two_n_factors again
    two_n_factors = {}
    for q, exp in N_factors.items():
        two_n_factors[q] = exp
    if 2 in two_n_factors:
        two_n_factors[2] += 1
    else:
        two_n_factors[2] = 1

    # Iterate all primes in two_n_factors
    for p_candidate in list(two_n_factors.keys()):
        # Check if exponent is 1
        if two_n_factors[p_candidate] != 1:
            continue
        # Check if p_candidate is a prime (since it's from N's factors or 2)
        # In the problem input, all given primes are primes, so p_candidate is prime if it's in N_factors or is 2 added
        # Compute product after removing one p_candidate
        product = 1
        for q, exp in two_n_factors.items():
            if q == p_candidate:
                if exp - 1 == 0:
                    continue
                product *= q ** (exp - 1)
            else:
                product *= q ** exp
        if product == p_candidate - 1:
            # Check if p_candidate is in N's factors and satisfies conditions a and b
            # p_candidate might be 2 added, which is not in N's factors
            # So need to check if p_candidate is a valid candidate
            # Check if p_candidate is in N's factors
            if p_candidate in N_factors:
                # Check condition a and b for p_candidate
                if N_factors[p_candidate] != 1:
                    continue
                valid = True
                for q in N_factors:
                    if q >= p_candidate and q != p_candidate:
                        valid = False
                        break
                if not valid:
                    continue
                print(p_candidate, 2)
                return
            else:
                # p_candidate is 2 added, check if all factors of N are less than p_candidate
                # and p_candidate is a prime (which it is, since 2 is added)
                # but N's factors must all be < p_candidate
                valid = True
                for q in N_factors:
                    if q >= p_candidate:
                        valid = False
                        break
                if valid:
                    # Also, check that in N's factors, p_candidate's exponent in two_n_factors is 1 (which it is)
                    print(p_candidate, 2)
                    return

    # If none found
    print(-1, -1)

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