結果

問題 No.981 一般冪乗根
ユーザー gew1fw
提出日時 2025-06-12 13:29:50
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,738 bytes
コンパイル時間 420 ms
コンパイル使用メモリ 82,212 KB
実行使用メモリ 64,652 KB
最終ジャッジ日時 2025-06-12 13:35:23
合計ジャッジ時間 38,817 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def mod_pow(a, b, mod):
    return pow(a, b, mod)

def mod_inverse(a, mod):
    return pow(a, -1, mod)

def tonelli_shanks(n, p):
    if n == 0:
        return 0
    if p == 2:
        return n
    if pow(n, (p - 1) // 2, p) != 1:
        return None
    if p % 4 == 3:
        x = pow(n, (p + 1) // 4, p)
        return x
    s = p - 1
    e = 0
    while s % 2 == 0:
        s //= 2
        e += 1
    for z in range(2, p):
        if pow(z, (p - 1) // 2, p) == p - 1:
            break
    c = pow(z, s, p)
    x = pow(n, (s + 1) // 2, p)
    t = pow(n, s, p)
    m = e
    while t != 1:
        temp = t
        i = 0
        while temp != 1 and i < m:
            temp = pow(temp, 2, p)
            i += 1
        if i == m:
            return None
        b = pow(c, 1 << (m - i - 1), p)
        x = (x * b) % p
        t = (t * b * b) % p
        c = (b * b) % p
        m = i
    return x

def solve():
    import sys
    input = sys.stdin.read().split()
    T = int(input[0])
    idx = 1
    for _ in range(T):
        p = int(input[idx])
        k = int(input[idx+1])
        a = int(input[idx+2])
        idx += 3
        if a == 0:
            print(0)
            continue
        d = math.gcd(k, p-1)
        m = (p-1) // d
        if pow(a, m, p) != 1:
            print(-1)
            continue
        k_prime = k // d
        try:
            t = pow(k_prime, -1, m)
        except ValueError:
            print(-1)
            continue
        y = pow(a, t, p)
        if d == 1:
            print(y % p)
        elif d == 2:
            x = tonelli_shanks(y, p)
            if x is None:
                print(-1)
            else:
                print(x % p)
        else:
            print(-1)

solve()
0