問題
素数 $P$ と整数 $A,B$（$1\le A,B
入力形式
A B P制約
$P$ は素数、$3 \le P \le 10^{12}$
$1 \le A, B < P$
$A \not\equiv 0 \pmod P$
入出力例
入力例1
2 11 13出力例1
72^7=128≡11 (mod13)。x=0..6では11にならず、x=7が最小。
入力例2
2 5 7出力例2
-12^x mod 7は1,2,4の巡回を繰り返し、5には決してならない。
ヒント（段階的開示）
ヒント1（方向性）
$x$を0から順に試すと最悪$O(P)$で$P\le10^{12}$では間に合わない。$x$を「大きい桁」と「小さい桁」に分け、両方をそれぞれ$O(\sqrt P)$個だけ調べるBaby-step Giant-step法（BSGS）を使う。
ヒント2（アプローチ）
$m=\lceil\sqrt P\rceil$として$x=im+j$（$0\le i\le m,0\le j
ヒント3（誘導）
m = math.isqrt(p) + 1
baby = {}
cur = 1
for j in range(m):
if cur not in baby:
baby[cur] = j
cur = cur * a % p
a_m_inv = pow(pow(a, m, p), p - 2, p) # (A^m)^{-1} mod p
gamma = b
for i in range(m + 1):
if gamma in baby:
answer = i * m + baby[gamma]
break
gamma = gamma * a_m_inv % p
else:
answer = -1模範解答 (Python)
import sys
import math
def solve():
a, b, p = map(int, sys.stdin.buffer.read().split())
a %= p
b %= p
m = math.isqrt(p) + 1
baby = {}
cur = 1 % p
for j in range(m):
if cur not in baby:
baby[cur] = j
cur = cur * a % p
a_m = pow(a, m, p)
a_m_inv = pow(a_m, p - 2, p)
gamma = b
ans = -1
for i in range(m + 1):
if gamma in baby:
ans = i * m + baby[gamma]
break
gamma = gamma * a_m_inv % p
print(ans)
solve()Step-by-Step 解説
1指数の平方分割
$x$を$0$から$P-2$まで探すのではなく$x=im+j$に分解する。$m\approx\sqrt P$で$i,j$ともに$O(\sqrt P)$通り。
$x$を$0$から$P-2$まで探すのではなく$x=im+j$に分解する。$m\approx\sqrt P$で$i,j$ともに$O(\sqrt P)$通り。
2baby-step（前計算）
$A^j \bmod P$（$j=0,\dots,m-1$）をハッシュ表に格納。同じ値は最小の$j$を優先し、最終的な$x$が最小になるようにする。
$A^j \bmod P$（$j=0,\dots,m-1$）をハッシュ表に格納。同じ値は最小の$j$を優先し、最終的な$x$が最小になるようにする。
3giant-step（探索）
$B\cdot(A^{-m})^i$を$i=0,1,2,\dots$と計算しながらハッシュ表に存在するか確認、見つかれば$x=im+j$を復元する。
$B\cdot(A^{-m})^i$を$i=0,1,2,\dots$と計算しながらハッシュ表に存在するか確認、見つかれば$x=im+j$を復元する。
4逆元の計算
$P$が素数なのでフェルマーの小定理$A^{P-2}\equiv A^{-1}$を使う。合成数の場合は拡張ユークリッドの互除法や一般化BSGSが必要。
$P$が素数なのでフェルマーの小定理$A^{P-2}\equiv A^{-1}$を使う。合成数の場合は拡張ユークリッドの互除法や一般化BSGSが必要。
5計算量と正当性
baby-step・giant-stepともに$O(\sqrt P)$、全体で$O(\sqrt P \log P)$。解が存在しない場合は$-1$を返す。
baby-step・giant-stepともに$O(\sqrt P)$、全体で$O(\sqrt P \log P)$。解が存在しない場合は$-1$を返す。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| baby-stepで同じ値のjを上書きする | 辞書への無条件代入 | if cur not in baby:で最初の（最小の）jのみ残す |
| Pが素数でないのにフェルマーの小定理で逆元を求める | 素数性の確認不足 | 合成数なら拡張ユークリッドや一般化BSGSを使う |
| mを浮動小数点sqrtの切り捨てで求め精度不足になる | float平方根の誤差 | math.isqrt(p)で正確な整数平方根を求める |
| iの探索範囲がmまでで境界のxを取りこぼす | xの最大値に対しiの範囲不足 | range(m+1)としてP-1未満の全域をカバーする |
次のステップ
- 発展: Pが合成数や$\gcd(A,P)\ne1$の場合の一般化BSGS、Pohlig-Hellman法との組み合わせ
- 次回予告: オフラインLCA（Tarjanのアルゴリズム）