結果

問題 No.981 一般冪乗根
ユーザー gew1fw
提出日時 2025-06-12 21:21:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,287 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 81,832 KB
実行使用メモリ 75,648 KB
最終ジャッジ日時 2025-06-12 21:23:22
合計ジャッジ時間 42,990 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None
    else:
        return x % m

def pow_mod(a, b, mod):
    result = 1
    a = a % mod
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % mod
        a = (a * a) % mod
        b = b // 2
    return result

def tonelli_shanks(n, p):
    if n == 0:
        return 0
    if p == 2:
        return p
    if pow_mod(n, (p - 1) // 2, p) != 1:
        return None
    if p % 4 == 3:
        x = pow_mod(n, (p + 1) // 4, p)
        return x
    q = p - 1
    s = 0
    while q % 2 == 0:
        q = q // 2
        s += 1
    for z in range(2, p):
        if pow_mod(z, q, p) != 1:
            break
    c = pow_mod(z, q, p)
    x = pow_mod(n, (q + 1) // 2, p)
    t = pow_mod(n, q, p)
    m = s
    while t != 1:
        i, temp = 0, t
        while temp != 1 and i < m:
            temp = pow_mod(temp, 2, p)
            i += 1
        if i == m:
            return None
        b = pow_mod(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_odd_root(b, s, p):
    g = gcd(s, p - 1)
    m = (p - 1) // g
    u = modinv(s, m)
    if u is None:
        return -1
    x = pow_mod(b, u, p)
    return x

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def solve(p, k, a):
    if a == 1:
        return 1
    if a == 0:
        return 0
    d = gcd(k, p - 1)
    e = (p - 1) // d
    if pow_mod(a, e, p) != 1:
        return -1
    k_prime = k // d
    m = e
    u = modinv(k_prime, m)
    if u is None:
        return -1
    b = pow_mod(a, u, p)
    s = d
    e = 0
    while s % 2 == 0:
        s = s // 2
        e += 1
    x = solve_odd_root(b, s, p)
    if x == -1:
        return -1
    for _ in range(e):
        x = tonelli_shanks(x, p)
        if x is None:
            return -1
    return x

def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        p, k, a = map(int, sys.stdin.readline().split())
        res = solve(p, k, a)
        print(res)

if __name__ == "__main__":
    main()
0