結果

問題 No.981 一般冪乗根
ユーザー LaikaLaika
提出日時 2020-02-07 23:37:40
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,295 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-04-17 20:42:35
合計ジャッジ時間 39,857 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 48 ms
10,880 KB
testcase_26 AC 48 ms
10,880 KB
testcase_27 WA -
testcase_28 WA -
evil_60bit1.txt WA -
evil_60bit2.txt WA -
evil_60bit3.txt WA -
evil_hack WA -
evil_hard_random WA -
evil_hard_safeprime.txt AC 195 ms
10,880 KB
evil_hard_tonelli0 WA -
evil_hard_tonelli1 WA -
evil_hard_tonelli2 WA -
evil_hard_tonelli3 WA -
evil_sefeprime1.txt AC 102 ms
10,880 KB
evil_sefeprime2.txt AC 103 ms
11,008 KB
evil_sefeprime3.txt AC 103 ms
10,880 KB
evil_tonelli1.txt WA -
evil_tonelli2.txt WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from functools import partial
from math import gcd

print = partial(print, flush=True)

def legendre(a, p):
    ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p-1 else ls

def mod_sqrt(a, p):
    if legendre(a, p) != 1:
        return 0
    elif a == 0:
        return 0
    elif p == 2:
        return 0
    elif p % 4 == 3:
        return pow(a, (p+1) // 4, p)

    s = p - 1
    e = 0
    while s % 2 == 0:
        s >>= 1
        e += 1

    n = 2
    while legendre(n, p) != -1:
        n += 1

    x = pow(a, (s+1) // 2, p)
    b = pow(a, s, p)
    g = pow(n, s, p)
    r = e

    while True:
        t = b
        m = 0
        for m in range(r):
            if t == 1:
                break
            t = pow(t, 2, p)

        if m == 0:
            return x

        gs = pow(g, 2 ** (r-m-1), p)
        g = (gs*gs) % p
        x = (x*gs) % p
        b = (b*g) % p
        r = m

t = int(input())

for i in range(t):
    p, k, a = map(int, input().split())
    if p == 2:
        print(1)
        continue
    m = 0
    n = k
    while n%2 == 0:
        m += 1
        n //= 2

    if gcd(n, p-1) == 1:
        l = pow(n, -1, p-1)
        x = pow(a, l, p)
        for _ in range(m):
            x = mod_sqrt(x, p)
        print(x if x != 0 else -1)
    else:
        print(-1)
0