結果

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

ソースコード

diff # 

def legendre(a, p):
    return pow(a, (p - 1) // 2, p)

# https://rosettacode.org/wiki/Tonelli-Shanks_algorithm#Python
def tonelli(n, p):
    assert legendre(n, p) == 1, "not a square (mod p)"
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    if s == 1:
        result = pow(n, (p + 1) // 4, p)
        return [result, p - result]
    for z in range(2, p):
        if p - 1 == legendre(z, p):
            break
    c = pow(z, q, p)
    r = pow(n, (q + 1) // 2, p)
    t = pow(n, q, p)
    m = s
    t2 = 0
    while (t - 1) % p != 0:
        t2 = (t * t) % p
        for i in range(1, m):
            if (t2 - 1) % p == 0:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        r = (r * b) % p
        c = (b * b) % p
        t = (t * c) % p
        m = i
    return [r, p - r]

memo = {}
def solve_two(a, n, p):
    if a == 0:
        return [0]
    if n == 1:
        return [a]
    if legendre(a, p) != 1:
        return []
    if (a, n, p) in memo:
        return memo[(a, n, p)]
    result = []
    for x in tonelli(a, p):
        result += solve_two(x, n // 2, p)
    memo[(a, n, p)] = result
    return result

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

def solve_odd(a, n, p):
    e = extgcd(n, p - 1)[0] % (p - 1)
    return pow(a, e, p)

def solve(a, n, p):
    e = 1
    while n % 2 == 0:
        n //= 2
        e *= 2
    a = solve_odd(a, n, p)
    return solve_two(a, e, p)

T = int(input())
for _ in range(T):
    p, k, a = map(int, input().split())
    answer = solve(a, k, p)
    if len(answer) == 0:
        print(-1)
    else:
        print(answer[0])
0