結果
問題 | No.981 一般冪乗根 |
ユーザー | toyuzuko |
提出日時 | 2022-04-13 00:11:36 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,782 bytes |
コンパイル時間 | 681 ms |
コンパイル使用メモリ | 86,876 KB |
実行使用メモリ | 1,002,604 KB |
最終ジャッジ日時 | 2023-08-23 10:11:41 |
合計ジャッジ時間 | 181,377 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | MLE | - |
testcase_01 | AC | 2,386 ms
172,008 KB |
testcase_02 | AC | 2,419 ms
244,216 KB |
testcase_03 | AC | 2,431 ms
238,284 KB |
testcase_04 | MLE | - |
testcase_05 | AC | 198 ms
433,284 KB |
testcase_06 | AC | 195 ms
152,912 KB |
testcase_07 | AC | 191 ms
152,796 KB |
testcase_08 | AC | 194 ms
152,720 KB |
testcase_09 | AC | 190 ms
153,060 KB |
testcase_10 | AC | 196 ms
77,888 KB |
testcase_11 | AC | 195 ms
77,744 KB |
testcase_12 | AC | 196 ms
77,832 KB |
testcase_13 | AC | 193 ms
77,480 KB |
testcase_14 | AC | 187 ms
77,892 KB |
testcase_15 | AC | 195 ms
77,572 KB |
testcase_16 | AC | 191 ms
77,356 KB |
testcase_17 | AC | 190 ms
78,068 KB |
testcase_18 | AC | 192 ms
77,800 KB |
testcase_19 | AC | 189 ms
77,620 KB |
testcase_20 | AC | 194 ms
77,724 KB |
testcase_21 | AC | 190 ms
77,528 KB |
testcase_22 | AC | 198 ms
77,480 KB |
testcase_23 | AC | 191 ms
77,560 KB |
testcase_24 | AC | 193 ms
77,756 KB |
testcase_25 | AC | 4,226 ms
201,512 KB |
testcase_26 | AC | 3,750 ms
193,980 KB |
testcase_27 | AC | 115 ms
77,032 KB |
testcase_28 | AC | 3,674 ms
194,856 KB |
evil_60bit1.txt | TLE | - |
evil_60bit2.txt | TLE | - |
evil_60bit3.txt | TLE | - |
evil_hack | AC | 93 ms
75,916 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 | TLE | - |
ソースコード
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 T = int(input()) for _ in range(T): p, k, a = map(int, input().split()) print(kth_root(k, a, p))