結果

問題 No.2207 pCr検査
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:02:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,728 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 456,192 KB
最終ジャッジ日時 2025-06-12 18:02:46
合計ジャッジ時間 6,505 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

# Precompute smallest prime factors up to 1e7
max_sieve = 10**7
spf = list(range(max_sieve + 1))

for i in range(2, int(max_sieve**0.5) + 1):
    if spf[i] == i:
        for j in range(i * i, max_sieve + 1, i):
            if spf[j] == j:
                spf[j] = i

# Read input
k = int(sys.stdin.readline())
factors = defaultdict(int)
for _ in range(k):
    p, e = map(int, sys.stdin.readline().split())
    factors[p] = e

# Check if N is a prime (k=1 and e=1)
if len(factors) == 1:
    primes = list(factors.keys())
    exponents = list(factors.values())
    if exponents[0] == 1:
        print(primes[0], 1)
        sys.exit()

# Collect candidates p with exponent 1
candidates = [p for p in factors if factors[p] == 1]

for p in candidates:
    # Compute M's factors (N / p)
    m_factors = defaultdict(int)
    for prime in factors:
        if prime == p:
            continue
        m_factors[prime] = factors[prime]
    
    # Iterate r from 2 to 60
    for r in range(2, 61):
        if r > p:
            continue
        
        # Generate terms p-1, p-2, ..., p - (r-1)
        terms = []
        valid = True
        for k in range(1, r):
            term = p - k
            if term <= 0:
                valid = False
                break
            terms.append(term)
        if not valid:
            continue
        
        # Factorize each term and accumulate product_factors
        product_factors = defaultdict(int)
        for term in terms:
            if term == 1:
                continue
            x = term
            while x != 1:
                prime = spf[x]
                count = 0
                while x % prime == 0:
                    count += 1
                    x = x // prime
                product_factors[prime] += count
        
        # Compute r! factors using Legendre's formula
        r_fact_factors = defaultdict(int)
        primes_in_r = []
        for q in range(2, r + 1):
            if spf[q] == q:
                primes_in_r.append(q)
        for q in primes_in_r:
            e = 0
            current = q
            while current <= r:
                e += r // current
                current *= q
            if e > 0:
                r_fact_factors[q] = e
        
        # Merge r! factors and M's factors
        merged_factors = defaultdict(int)
        for q in r_fact_factors:
            merged_factors[q] += r_fact_factors[q]
        for q in m_factors:
            merged_factors[q] += m_factors[q]
        
        # Compare product_factors and merged_factors
        if product_factors == merged_factors:
            print(p, r)
            sys.exit()

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