#753532 (PyPy3) No.981 一般冪乗根

提出ソース

結果

問題	No.981 一般冪乗根
ユーザー	toyuzuko
提出日時	2022-04-12 23:33:23
言語	PyPy3 (7.3.15)
結果	MLE (最新) AC (最初)
実行時間	-
コード長	7,495 bytes
コンパイル時間	159 ms
コンパイル使用メモリ	82,256 KB
実行使用メモリ	901,920 KB
最終ジャッジ日時	2024-06-01 06:47:30
合計ジャッジ時間	170,171 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2,398 ms 172,288 KB
testcase_01	MLE	-
testcase_02	AC	2,436 ms 177,116 KB
testcase_03	AC	2,384 ms 229,060 KB
testcase_04	AC	2,236 ms 392,908 KB
testcase_05	MLE	-
testcase_06	MLE	-
testcase_07	AC	177 ms 140,448 KB
testcase_08	AC	179 ms 140,888 KB
testcase_09	AC	178 ms 142,048 KB
testcase_10	AC	179 ms 77,872 KB
testcase_11	AC	178 ms 77,696 KB
testcase_12	AC	178 ms 77,636 KB
testcase_13	AC	180 ms 78,084 KB
testcase_14	AC	179 ms 77,872 KB
testcase_15	AC	180 ms 77,776 KB
testcase_16	AC	176 ms 77,704 KB
testcase_17	AC	173 ms 77,788 KB
testcase_18	AC	179 ms 77,656 KB
testcase_19	AC	172 ms 77,744 KB
testcase_20	AC	179 ms 77,748 KB
testcase_21	AC	174 ms 77,844 KB
testcase_22	AC	181 ms 77,940 KB
testcase_23	AC	174 ms 77,816 KB
testcase_24	AC	179 ms 77,872 KB
testcase_25	AC	4,226 ms 201,668 KB
testcase_26	AC	3,764 ms 197,372 KB
testcase_27	AC	102 ms 77,392 KB
testcase_28	AC	3,715 ms 192,740 KB
evil_60bit1.txt	TLE	-
evil_60bit2.txt	TLE	-
evil_60bit3.txt	TLE	-
evil_hack	AC	57 ms 64,864 KB
evil_hard_random	MLE	-
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	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

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(1)

from math import gcd, sqrt

def primitive_root(m):
    if m == 2: return 1
    divs = set(P.factorize_naive(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))

yukicoder

結果

テストケース

ソースコード