結果

問題 No.2207 pCr検査
ユーザー gew1fw
提出日時 2025-06-12 20:01:51
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,354 bytes
コンパイル時間 305 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 169,296 KB
最終ジャッジ日時 2025-06-12 20:05:34
合計ジャッジ時間 5,684 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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])
        idx += 2
        n_factors[p] = e

    for p in list(n_factors.keys()):
        # Check if all other primes are <= p
        valid = True
        for q in n_factors.keys():
            if q > p:
                valid = False
                break
        if not valid:
            continue

        # Handle q = p case: exponent must be exactly 1
        if n_factors[p] != 1:
            continue

        # Precompute E_p for each q (other than p)
        E_p = {}
        for q in n_factors.keys():
            if q == p:
                continue
            e = 0
            current = q
            while current <= p - 1:
                e += (p - 1) // current
                current *= q
            E_p[q] = e

        # Check if any q (other than p) has exponent_N > E_p[q]
        valid = True
        for q in n_factors.keys():
            if q == p:
                continue
            if n_factors[q] > E_p.get(q, 0):
                valid = False
                break
        if not valid:
            continue

        # Try possible r values
        max_r = min(p - 1, 10**5)
        for r in range(1, max_r + 1):
            match = True
            for q in n_factors.keys():
                if q == p:
                    if n_factors[q] != 1:
                        match = False
                        break
                    continue

                # Compute E_r(q)
                e_r = 0
                current = q
                while current <= r:
                    e_r += r // current
                    current *= q

                # Compute E_{p - r}(q)
                e_p_minus_r = 0
                current = q
                while current <= (p - r):
                    e_p_minus_r += (p - r) // current
                    current *= q

                # Compute exponent_in_C
                exponent_in_C = E_p[q] - (e_r + e_p_minus_r)

                if exponent_in_C != n_factors[q]:
                    match = False
                    break
            if match:
                print(p, r)
                return

    print(-1, -1)

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