Day 174-Q5 — 2026-10-10 | 多数クエリの離散対数（Pohlig–Hellman の素因数ごとに、BSGS の表を √(T·a·r) に広げて共有する）

📋 コピーimport sys
from math import isqrt


def factor(n):
    # n < 10^12: 10^6 までの試し割りで、残りは 1 か素数
    fac = {}
    d = 2
    while d * d <= n:
        if n % d == 0:
            c = 0
            while n % d == 0:
                n //= d
                c += 1
            fac[d] = c
        d += 1 if d == 2 else 2
    if n > 1:
        fac[n] = fac.get(n, 0) + 1
    return fac


def main():
    data = sys.stdin.buffer.read().split()
    p, g, t = int(data[0]), int(data[1]), int(data[2])
    hs = [int(x) for x in data[3:3 + t]]
    n = p - 1
    fac = factor(n)

    parts = []                                  # (r, a, g_r, 表, 巨人の歩幅 g_r^{-m}, m)
    for r, a in fac.items():
        gr = pow(g, n // r, p)                  # 位数 r の元
        # 表の大きさ: 表を作る m 回と、全クエリの巨人の歩み T*a*r/m 回の和を最小に
        m = min(r, max(1, isqrt(r * t * a)))
        table = {}
        cur = 1
        for j in range(m):
            table.setdefault(cur, j)
            cur = cur * gr % p
        giant = pow(cur, p - 2, p)              # g_r^{-m}
        parts.append((r, a, gr, table, giant, m))

    out = []
    for h in hs:
        x_all, md = 0, 1
        for r, a, gr, table, giant, m in parts:
            x = 0
            ra = 1
            for j in range(a):                  # r 進で 1 桁ずつ
                y = pow(h * pow(g, n - x, p) % p, n // (ra * r), p)
                d = None
                for i in range(r // m + 1):
                    if y in table:
                        d = i * m + table[y]
                        break
                    y = y * giant % p
                x += d * ra
                ra *= r
            mod = ra                            # CRT で x mod r^a を合わせる
            tt = (x - x_all) * pow(md, -1, mod) % mod
            x_all += md * tt
            md *= mod
        out.append(x_all % n)
    print('\n'.join(map(str, out)))


main()