結果
| 問題 | No.981 一般冪乗根 |
| ユーザー |
 toyuzuko
|
| 提出日時 | 2022-04-12 23:18:18 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 3,973 ms / 6,000 ms |
| コード長 | 7,494 bytes |
| コンパイル時間 | 269 ms |
| コンパイル使用メモリ | 87,268 KB |
| 実行使用メモリ | 209,464 KB |
| 最終ジャッジ日時 | 2023-08-23 08:53:50 |
| 合計ジャッジ時間 | 173,574 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,482 ms
181,368 KB |
| testcase_01 | AC | 2,384 ms
172,504 KB |
| testcase_02 | AC | 2,465 ms
174,960 KB |
| testcase_03 | AC | 2,398 ms
170,172 KB |
| testcase_04 | AC | 2,297 ms
167,328 KB |
| testcase_05 | AC | 297 ms
84,632 KB |
| testcase_06 | AC | 302 ms
84,336 KB |
| testcase_07 | AC | 292 ms
84,660 KB |
| testcase_08 | AC | 302 ms
84,916 KB |
| testcase_09 | AC | 303 ms
84,944 KB |
| testcase_10 | AC | 304 ms
84,720 KB |
| testcase_11 | AC | 294 ms
84,460 KB |
| testcase_12 | AC | 297 ms
84,828 KB |
| testcase_13 | AC | 296 ms
84,296 KB |
| testcase_14 | AC | 289 ms
84,348 KB |
| testcase_15 | AC | 296 ms
84,952 KB |
| testcase_16 | AC | 297 ms
84,724 KB |
| testcase_17 | AC | 289 ms
85,028 KB |
| testcase_18 | AC | 297 ms
84,584 KB |
| testcase_19 | AC | 292 ms
84,304 KB |
| testcase_20 | AC | 296 ms
84,556 KB |
| testcase_21 | AC | 291 ms
84,440 KB |
| testcase_22 | AC | 298 ms
84,704 KB |
| testcase_23 | AC | 296 ms
84,680 KB |
| testcase_24 | AC | 293 ms
84,428 KB |
| testcase_25 | AC | 3,973 ms
209,464 KB |
| testcase_26 | AC | 3,564 ms
202,844 KB |
| testcase_27 | AC | 195 ms
84,392 KB |
| testcase_28 | AC | 3,837 ms
202,308 KB |
| evil_60bit1.txt | TLE | - |
| evil_60bit2.txt | TLE | - |
| evil_60bit3.txt | TLE | - |
| evil_hack | AC | 252 ms
81,448 KB |
| evil_hard_random | TLE | - |
| evil_hard_safeprime.txt | TLE | - |
| evil_hard_tonelli0 | TLE | - |
| evil_hard_tonelli1 | TLE | - |
| evil_hard_tonelli2 | TLE | - |
| evil_hard_tonelli3 | TLE | - |
| evil_sefeprime1.txt | TLE | - |
| evil_sefeprime2.txt | TLE | - |
| evil_sefeprime3.txt | TLE | - |
| evil_tonelli1.txt | TLE | - |
| evil_tonelli2.txt | MLE | - |
ソースコード
from random import randint
from collections import Counter
class Prime():
def __init__(self, m=10**6):
self.m = m
self.isprime = [True] * (m + 1)
self.minfac = [-1] * (m + 1)
self.mobius = [1] * (m + 1)
self.isprime[0] = self.isprime[1] = False
self.minfac[1] = 1
for p in range(2, m + 1):
if not self.isprime[p]: continue
self.minfac[p] = p
self.mobius[p] = -1
for q in range(2 * p, m + 1, p):
self.isprime[q] = False
if self.minfac[q] == -1:
self.minfac[q] = p
if (q // p) % p:
self.mobius[q] *= -1
else:
self.mobius[q] = 0
def gcd(self, x, y):
while y:
x, y = y, x % y
return x
def lcm(self, x, y):
return x // self.gcd(x, y) * y
def is_prime(self, n):
if n <= self.m:
return self.isprime[n]
if not n & 1:
return False
return self.miller_rabin(n)
def miller_rabin(self, n):
if n <= 4294967295:
p = [2, 7, 61]
elif n <= 281474976710655:
p = [2, 3, 5, 7, 11, 13, 17]
elif n <= 18446744073709551615:
p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
else:
p = [randint(1, n - 1) for _ in range(20)]
d = n - 1
d = d // (d & -d)
for a in p:
t = d
y = pow(a, t, n)
if y == 1: continue
while y != n - 1:
y = (y * y) % n
if y == 1 or t == n - 1: return False
t <<= 1
return True
def factorize(self, n):
if n <= self.m:
return self.factorize_fast(n)
if self.is_prime(n):
return [n]
res = []
stack = [n]
while stack:
tmp = stack.pop()
if tmp <= self.m:
res.extend(self.factorize_fast(tmp))
continue
p = self.pollard_rho(tmp)
q = tmp // p
pri_p = self.is_prime(p)
pri_q = self.is_prime(q)
if pri_p and pri_q:
res.append(p)
res.append(q)
elif pri_p:
res.append(p)
while not q % p:
res.append(p)
q //= p
if self.is_prime(q):
res.append(q)
else:
stack.append(q)
elif pri_q:
res.append(q)
while not p % q:
res.append(q)
p //= q
if self.is_prime(p):
res.append(p)
else:
stack.append(p)
else:
stack.append(p)
stack.append(q)
return sorted(res)
def factorize_fast(self, n):
res = []
while n > 1:
p = self.minfac[n]
while self.minfac[n] == p:
n //= p
res.append(p)
return sorted(res)
def factorize_naive(self, n):
res = []
x, y = n, 2
while y * y <= x:
while not x % y:
res.append(y)
x //= y
y += 1
if x > 1:
res.append(x)
return sorted(res)
def pollard_rho(self, n):
m = int(n**0.125) + 1
s = randint(1, 1000)
while True:
y, r, q = 2, 1, 1
d = 1
while d == 1:
x = y
for _ in range(r):
y = (y * y + s) % n
for k in range(0, r, m):
ys = y
for i in range(min(m, r - k)):
y = (y * y + s) % n
q = q * abs(x - y) % n
d = self.gcd(n, q)
if d != 1:
break
r <<= 1
if d == n:
while d == 1:
ys = (ys * ys + s) % n
d = self.gcd(n, abs(x - ys))
if d != n:
break
s += 1
return d
def divisors(self, n):
if n <= self.m:
return self.divisors_fast(n)
if self.is_prime(n):
return [1, n]
return self.divisors_naive(n)
def divisors_fast(self, n):
res = [1]
f = Counter(self.factorize_fast(n))
for p, d in f.items():
s = len(res)
for i in range(s):
v = 1
for j in range(d):
v *= p
res.append(res[i] * v)
return sorted(res)
def divisors_naive(self, n):
res = []
x, y = n, 1
while y * y < x:
if not x % y:
res.append(y)
res.append(x // y)
y += 1
if y * y == x:
res.append(y)
return sorted(res)
def zeta_transform(self, arr):
n = len(arr)
assert n <= self.m
res = arr.copy()
for p in range(2, n):
if not self.isprime[p]:
continue
for k in range(1, (n - 1) // p + 1)[::-1]:
res[k] += res[k * p]
return res
def mobius_transform(self, arr):
n = len(arr)
assert n <= self.m
res = arr.copy()
for p in range(2, n):
if not self.isprime[p]:
continue
for k in range(p, n, p):
res[k // p] -= res[k]
return res
def convolution_gcd(self, f, g):
assert len(f) == len(g)
F = self.zeta_transform(f)
G = self.zeta_transform(g)
H = [u * v for u, v in zip(F, G)]
h = self.mobius_transform(H)
return h
P = Prime(100000)
from math import gcd, sqrt
def primitive_root(m):
if m == 2: return 1
divs = set(P.factorize(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
T = int(input())
for _ in range(T):
p, k, a = map(int, input().split())
print(kth_root(k, a, p))