結果

問題 No.2207 pCr検査
コンテスト
ユーザー dachengz
提出日時 2023-02-06 12:12:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,620 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 358,392 KB
最終ジャッジ日時 2024-07-04 17:13:21
合計ジャッジ時間 7,014 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import gcd, log

def deg(P, p):
    ret = 0
    P //= p
    while P:
        ret += P
        P //= p
    return ret

def isqrt(n):
    if n <= 0:
        return 0

    x = int((n ** 0.5) * (1 + 1e-14))
    while True:
        y = (x + n // x) // 2
        if y >= x:
            return x
        x = y

def smf_sieve(N):
    v = isqrt(N)
    smf = list(range(N + 1))
    for d in range(2, N + 1, 2):
        smf[d] = 2
    for p in range(3, v + 1, 2):
        if smf[p] != p:
            continue
        for d in range(p * p, N + 1, 2 * p):
            if smf[d] == d:
                smf[d] = p
    return smf

k = int(input())
pe = []
for _ in range(k):
    pe.append([int(x) for x in input().split()])
P = pe[-1][0]
P1 = P + 1
needmod = 1
needlog = 0.0
for p, e in pe:
    if e > deg(P, p):
        print(-1, -1)
        exit
    needmod = needmod * pow(p, e, P) % P
    needlog += log(p) * e

inv = [1] * P1
for i in range(2, P1):
    inv[i] = P - P // i * inv[P % i] % P

has = [0] * P1
smf = smf_sieve(P)
currlog = 0.0
currmod = 1
for r in range(1, P // 2 + 1):
    currlog += log(P1 - r) - log(r)
    currmod = currmod * (P1 - r) % P1 * inv[r] % P1
    if currlog - needlog > 1e-5:
        print(-1, -1)
        exit
    m = P1 - r
    while m > 1:
        p = smf[m]
        while smf[m] == p:
            m //= p
            has[p] += 1
    m = r
    while m > 1:
        p = smf[m]
        while smf[m] == p:
            m //= p
            has[p] -= 1
    if currlog - needlog < -1e-5 or currmod != needmod:
        continue
    if all(has[p] == e for p, e in pe):
        print(P, r)
        exit
0