Day 180-Q4 — 2026-10-16 | 法 p の K 乗根（p−1 の素因数ごとの部分群に分け、K と互いに素な部分は逆元、そうでない部分は Pohlig–Hellman＋BSGS で離散対数。「素因数ごとに順に根を取る」が途中の根の選び方で失敗する例つき）

📋 コピーimport sys
from math import gcd, isqrt


def factor_small(n):
    """n <= 10^9 程度を試し割りで素因数分解"""
    fs = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            fs[d] = fs.get(d, 0) + 1
            n //= d
        d += 1 if d == 2 else 2
    if n > 1:
        fs[n] = fs.get(n, 0) + 1
    return fs


def dlog_prime_order(h, a, q, p):
    """h の位数が素数 q のとき h^L = a となる L (0<=L<q) を BSGS で"""
    m = isqrt(q - 1) + 1
    table = {}
    e = 1
    for j in range(m):
        if e not in table:
            table[e] = j
        e = e * h % p
    step = pow(h, q - m, p)          # h^(-m)
    g = a
    for i in range(m):
        j = table.get(g)
        if j is not None:
            return i * m + j
        g = g * step % p
    raise ValueError("no log")


def dlog_sylow(h, a, q, t, p):
    """h の位数が q^t、a が <h> に入るとき h^L = a の L を Pohlig–Hellman で桁ごとに"""
    gamma = pow(h, q ** (t - 1), p)  # 位数 q
    L = 0
    qk = 1
    hinv = pow(h, p - 2, p)
    for k in range(t):
        # (h^-L * a)^(q^(t-1-k)) = gamma^(d_k)
        cur = pow(pow(hinv, L, p) * a % p, q ** (t - 1 - k), p)
        d = dlog_prime_order(gamma, cur, q, p) if q > 1 else 0
        L += d * qk
        qk *= q
    return L


def kth_root(k, y, p, fs):
    """x^k ≡ y (mod p) の解の個数と解を 1 つ。k >= 1"""
    y %= p
    if y == 0:
        return 1, 0
    n = p - 1
    g = gcd(k, n)
    if pow(y, n // g, p) != 1:
        return 0, -1
    x = 1
    for q, t in fs.items():
        qt = q ** t
        rest = n // qt
        # y の q 成分 y_q = y^(rest * inv(rest) mod qt)：位数 q^t の部分群へ射影
        eps = rest * pow(rest, -1, qt) % n
        yq = pow(y, eps, p)
        e = 0
        kk = k
        while kk % q == 0 and e < t:
            kk //= q
            e += 1
        if e == 0:
            xq = pow(yq, pow(k % qt, -1, qt), p)
        else:
            # 位数 q^t の生成元 h = z^rest（z は q 乗非剰余）
            z = 2
            while pow(z, n // q, p) == 1:
                z += 1
            h = pow(z, rest, p)
            L = dlog_sylow(h, yq, q, t, p)   # q^e | L は剰余判定で保証
            mod = q ** (t - e)
            M = (L // q ** e) * pow(kk % mod, -1, mod) % mod if mod > 1 else 0
            xq = pow(h, M, p)
        x = x * xq % p
    return g, x


def main():
    data = sys.stdin.buffer.read().split()
    T = int(data[0])
    out = []
    pos = 1
    cache = {}
    for _ in range(T):
        k = int(data[pos]); y = int(data[pos + 1]); p = int(data[pos + 2]); pos += 3
        if p not in cache:
            cache[p] = factor_small(p - 1)
        c, x = kth_root(k, y, p, cache[p])
        out.append(f"{c} {x}")
    sys.stdout.write("\n".join(out) + "\n")


main()