結果

問題 No.981 一般冪乗根
ユーザー Laika
提出日時 2020-02-07 23:37:40
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,295 bytes
コンパイル時間 363 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-10-09 14:41:30
合計ジャッジ時間 43,911 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 38
権限があれば一括ダウンロードができます

ソースコード

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