Day 168-Q5 — 2026-10-03 | 離散対数（法が素数でなくてもよい BSGS。gcd を割って互いに素にし、途中の一致も拾う）

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


def discrete_log(a, b, m):
    # 最小の x >= 0 で a^x ≡ b (mod m)。無ければ -1
    a %= m
    b %= m
    if m == 1:
        return 0
    k = 1 % m
    cnt = 0
    while True:
        if k == b:
            return cnt                      # a^cnt ≡ b を、gcd を割る途中でも検出する
        g = gcd(a, m)
        if g == 1:
            break
        if b % g:
            return -1
        b //= g
        m //= g
        k = k * (a // g) % m
        cnt += 1
    # ここから gcd(a, m) = 1。k * a^x ≡ b (mod m) を解く（baby-step giant-step）
    s = isqrt(m) + 1
    table = {}
    cur = b
    for j in range(s):                      # b * a^j を覚える（同じ値は大きい j を残す）
        table[cur] = j
        cur = cur * a % m
    step = pow(a, s, m)
    cur = k
    for i in range(1, s + 1):
        cur = cur * step % m                # k * a^(s i)
        if cur in table:
            x = i * s - table[cur]
            if x >= 0:
                return x + cnt
    return -1


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    for i in range(t):
        a, b, m = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])
        out.append(discrete_log(a, b, m))
    print("\n".join(map(str, out)))


if __name__ == "__main__":
    main()