結果

問題 No.981 一般冪乗根
ユーザー semisagisemisagi
提出日時 2020-12-10 16:23:46
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,741 bytes
コンパイル時間 87 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-09-19 20:37:00
合計ジャッジ時間 39,418 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 56 ms
11,136 KB
testcase_26 AC 49 ms
11,008 KB
testcase_27 RE -
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 302 ms
11,776 KB
evil_hard_tonelli0 WA -
evil_hard_tonelli1 WA -
evil_hard_tonelli2 WA -
evil_hard_tonelli3 WA -
evil_sefeprime1.txt AC 125 ms
11,136 KB
evil_sefeprime2.txt AC 129 ms
11,008 KB
evil_sefeprime3.txt AC 133 ms
11,136 KB
evil_tonelli1.txt WA -
evil_tonelli2.txt WA -
権限があれば一括ダウンロードができます

ソースコード

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