結果
問題 | No.981 一般冪乗根 |
ユーザー |
![]() |
提出日時 | 2020-02-09 01:01:42 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,478 bytes |
コンパイル時間 | 300 ms |
コンパイル使用メモリ | 82,200 KB |
実行使用メモリ | 551,044 KB |
最終ジャッジ日時 | 2024-10-09 21:04:21 |
合計ジャッジ時間 | 184,544 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 29 TLE * 14 MLE * 1 |
ソースコード
def primeFactor(N):i = 2ret = {}n = NmrFlg = 0while i*i <= n:k = 0while n % i == 0:n //= ik += 1if k: ret[i] = ki += 1 + i%2if i == 101 and n >= 2**20:def findFactorRho(N):def gcd(a, b):while b: a, b = b, a % breturn adef f(x, c):return (x * x + c) % Nfor c in range(1, 99):X, d, j = [2], 1, 0while d == 1:j += 1X.append(f(X[-1], c))X.append(f(X[-1], c))d = gcd(abs(X[2*j]-X[j]), N)if d != N:if isPrimeMR(d):return delif isPrimeMR(N//d): return N//dwhile n > 1:if isPrimeMR(n):ret[n], n = 1, 1else:mrFlg = 1j = findFactorRho(n)k = 0while n % j == 0:n //= jk += 1ret[j] = kif n > 1: ret[n] = 1if mrFlg > 0: ret = {x: ret[x] for x in sorted(ret)}return retdef isPrimeMR(n):if n == 2:return Trueif n == 1 or n & 1 == 0:return Falsed = (n - 1) >> 1while d & 1 == 0:d >>= 1L = [2, 7, 61] if n < 1<<32 else [2, 13, 23, 1662803] if n < 1<<40 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19,23, 29]for a in L:t = dy = pow(a, t, n)while t != n - 1 and y != 1 and y != n - 1:y = (y * y) % nt <<= 1if y != n - 1 and t & 1 == 0:return Falsereturn Truedef discrete_logarithm(a, b, mod):a %= modb %= modm = int(mod**0.5+0.9) + 1s = 1for i in range(m):if s == b:return is = s * a % modinva = pow(a, mod-2, mod)am = pow(a, m, mod)D = {}k = bfor i in range(m):if k not in D:D[k] = ik = k * inva % modk = 1for i in range(m):if k in D:return D[k] + i * mk = k * am % modreturn -1def primitive_root(mod, pf):for i in range(1, mod):for q in pf:if pow(i, (mod-1) // q, mod) == 1:breakelse:return idef gcd(a, b):while b: a, b = b, a % breturn abs(a)def inv(x, nn):def invv(a, n):if a == 1: return (1, 0)if a == 0: return (-1, -1)b, m = a, nwhile m != 0: b,m = m,b%mif b > 1: return (-1, -1)k = n // ay, yy = invv(n % a, a)if y < 0: return (-1, -1)x = yy - k * ywhile x < 0:x += ny -= areturn (x, y)return invv(x, nn)[0]T = int(input())for _ in range(T):p, k, a = map(int, input().split())pp = p-1pf = primeFactor(pp)h = primitive_root(p, pf)b = discrete_logarithm(h, a, p)while True:g = gcd(k, pp)if g == 1: breakif b % g:print(-1)breakb //= gk //= gpp //= gif g > 1: continueprint(pow(h, b * inv(k, pp) % pp, p))