結果

問題 No.2207 pCr検査
ユーザー dachengzdachengz
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
58,240 KB
testcase_01 WA -
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

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