結果
| 問題 | No.981 一般冪乗根 |
| ユーザー |
 toyuzuko
|
| 提出日時 | 2022-04-12 23:50:25 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,827 bytes |
| コンパイル時間 | 89 ms |
| コンパイル使用メモリ | 12,928 KB |
| 実行使用メモリ | 22,224 KB |
| 最終ジャッジ日時 | 2024-06-01 06:58:50 |
| 合計ジャッジ時間 | 15,497 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| evil_60bit1.txt | -- | - |
| evil_60bit2.txt | -- | - |
| evil_60bit3.txt | -- | - |
| evil_hack | -- | - |
| evil_hard_random | -- | - |
| evil_hard_safeprime.txt | -- | - |
| evil_hard_tonelli0 | -- | - |
| evil_hard_tonelli1 | -- | - |
| evil_hard_tonelli2 | -- | - |
| evil_hard_tonelli3 | -- | - |
| evil_sefeprime1.txt | -- | - |
| evil_sefeprime2.txt | -- | - |
| evil_sefeprime3.txt | -- | - |
| evil_tonelli1.txt | -- | - |
| evil_tonelli2.txt | -- | - |
ソースコード
from math import gcd, sqrt
def prime_factor(n):
res = []
x, y = n, 2
while y * y <= x:
if not x % y:
res.append(y)
while not x % y:
x //= y
y += 1
if x > 1:
res.append(x)
return res
def primitive_root(m):
if m == 2: return 1
divs = prime_factor(m - 1)
g = 2
while True:
for d in divs:
if pow(g, (m - 1) // d, m) == 1: break
else:
return g
g += 1
def discrete_logarithm(x, y, m):
if m == 1: return 0
if y == 1: return 0
if x == y == 0: return 1
sq = int(sqrt(m)) + 1
powx = {}
p = 1
for i in range(sq + 1):
if p % m == y: return i
powx[p * y % m] = i
p *= x
p %= m
z = pow(x, sq, m)
g = z
for i in range(1, sq + 1):
if g in powx:
res = i * sq - powx[g]
if pow(x, res, m) == y: return res
g *= z
g %= m
return -1
def inv_gcd(a, b):
a %= b
if a == 0: return b, 0
s, t, m0, m1 = b, a, 0, 1
while t:
u = s // t
s -= t * u
m0 -= m1 * u
s, t = t, s
m0, m1 = m1, m0
if m0 < 0: m0 += b // s
return s, m0
def inv_mod(x, m):
g, im = inv_gcd(x, m)
return im
def kth_root(k, y, p):
if k == 0:
if y == 1:
return 0
else:
return -1
if y == 0:
return 0
g = gcd(k, p - 1)
m = (p - 1) // g
if pow(a, m, p) != 1: return -1
r = primitive_root(p)
l = discrete_logarithm(r, y, p)
if l % g: return -1
res = pow(r, l // g * inv_mod(k // g, m) % m, p)
return res
import sys
input = sys.stdin.buffer.readline
T = int(input())
for _ in range(T):
p, k, a = map(int, input().split())
print(kth_root(k, a, p))