Day 031-Q4 — 拡張ユークリッド互除法・線形合同式・BSGS

2026-05-14 赤色 / Phase 8+ ★★★★★★★★★ 整数論

問題

線形合同式（Type 1）、連立合同式 CRT（Type 2）、離散対数 BSGS（Type 3）の 3 種クエリに答えよ。

制約

$1 \le Q \le 10^5$
$1 \le m, m_1, m_2, n \le 10^9$

入出力例

入力例 1

4
1 6 10 14
1 3 6 9
2 2 3 3 5
3 2 32 1000000007

出力例 1

4
2
8 15
-1

ヒント (段階的開示)

ヒント1: 方向性
Type 1: ext_gcd で逆元 / Type 2: 一般 CRT / Type 3: BSGS（一般版）。
ヒント2: アプローチ
$\gcd(a, m) \mid b$ が解存在条件。$x = s \cdot (b/g) \bmod (m/g)$。CRT は $r_1 + m_1 k$ 形で Type 1 に帰着。
ヒント3: 一般 BSGS
$\gcd(a,n) > 1$ なら前処理で $\gcd$ を剥がしてから通常 BSGS。

模範解答 (Python)

import sys
from sys import stdin
from math import isqrt, gcd

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    return g, y, x - (a // b) * y

def linear_congruence(a, b, m):
    a %= m; b %= m
    if a == 0:
        return 0 if b == 0 else -1
    g, s, _ = ext_gcd(a, m)
    if b % g != 0:
        return -1
    mod = m // g
    x0 = s * (b // g) % mod
    return x0 % mod

def crt(r1, m1, r2, m2):
    g = gcd(m1, m2)
    if (r2 - r1) % g != 0:
        return -1, -1
    lcm = m1 // g * m2
    _, s, _ = ext_gcd(m1, m2)
    k = s * ((r2 - r1) // g) % (m2 // g)
    x = (r1 + m1 * k) % lcm
    if x < 0:
        x += lcm
    return x, lcm

def bsgs(a, b, n):
    t = 0
    cur_n = n
    while True:
        g = gcd(a, cur_n)
        if g == 1:
            break
        if b % g != 0:
            return -1
        b //= g
        cur_n //= g
        t += 1
        if t > 100:
            return -1
    m = isqrt(cur_n) + 1
    b_table = {}
    val = b % cur_n
    for j in range(m):
        if val not in b_table:
            b_table[val] = j
        val = val * a % cur_n
    am = pow(a, m, cur_n)
    val = am
    for i in range(1, m + 1):
        if val in b_table:
            x = m * i - b_table[val]
            if x >= 0:
                return x + t
        val = val * am % cur_n
    return -1

def solve():
    sys.setrecursionlimit(200000)
    data = stdin.read().split()
    idx = 0
    Q = int(data[idx]); idx += 1
    out = []
    for _ in range(Q):
        qtype = int(data[idx]); idx += 1
        if qtype == 1:
            a, b, m = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
            out.append(str(linear_congruence(a, b, m)))
        elif qtype == 2:
            r1, m1, r2, m2 = int(data[idx]), int(data[idx+1]), int(data[idx+2]), int(data[idx+3]); idx += 4
            x, lcm = crt(r1, m1, r2, m2)
            out.append('-1' if x == -1 else f'{x} {lcm}')
        elif qtype == 3:
            a, b, n = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
            out.append(str(bsgs(a, b, n)))
    print('\n'.join(out))

solve()

Step-by-Step 解説

1拡張ユークリッド
$\gcd(a,b) = as + bt$ を再帰で $O(\log \min(a,b))$。
2線形合同式
解存在 ⟺ $g \mid b$。解 $\equiv s \cdot b/g \pmod{m/g}$。
3一般 CRT
$g = \gcd(m_1, m_2)$、解存在 ⟺ $g \mid r_2 - r_1$。
4BSGS
$x = mi - j$ 分解、ハッシュ + giant step で $O(\sqrt{n})$。
5一般 BSGS
前処理で $\gcd(a,n)$ を剥がし、$t$ を解に加算。

よくあるミス

ミス原因正しい書き方
$g \nmid b$ チェック忘れ解存在条件漏れ必ず確認
CRT の lcm オーバーフロー$m_1 \cdot m_2$ が大きいm1 // g * m2
BSGS で x < 0$mi - j$ 負になるx >= 0 をチェック
最小非負解でない負の値が返る% mod 後に補正

次のステップ

  • $K$ 個の連立 CRT + Garner

自己評価

自分の回答

気づき・メモ