問題
素数 p と整数 g, y が与えられる。$g^x \equiv y \pmod{p}$ となる最小非負整数 x を求めよ。なければ -1。
制約
$1 \le T \le 100$
素数 $p \le 10^9$
$1 \le g, y < p$
入出力例
入力例 1
3
2 3 5
3 7 11
2 1 1000000007出力例 1
3
-1
0ヒント (段階的開示)
ヒント1: 方向性
$x = i + j m$ ($m \approx \sqrt{p}$) に分解。$g^i \equiv y (g^{-m})^j \pmod p$。
ヒント2: アプローチ
Baby: $g^i$ をハッシュに保存。Giant: $y (g^{-m})^j$ を計算してテーブルを引く。
ヒント3: 誘導
$g^{-m}$ はフェルマー小定理: $(g^m)^{p-2} \bmod p$。
模範解答 (Python)
import sys
import math
input = sys.stdin.readline
def bsgs(g, y, p):
if y == 1:
return 0
if g == 0:
return -1
m = math.isqrt(p) + 1
baby = {}
val = 1
for i in range(m):
if val not in baby:
baby[val] = i
val = val * g % p
gm = pow(g, m, p)
gm_inv = pow(gm, p - 2, p)
val = y % p
for j in range(m + 1):
if val in baby:
x = baby[val] + j * m
if pow(g, x, p) == y % p:
return x
val = val * gm_inv % p
return -1
def main():
T = int(input())
for _ in range(T):
g, y, p = map(int, input().split())
print(bsgs(g, y, p))
main()Step-by-Step 解説
1分解
$x = i + jm$ ($0 \le i < m$, $0 \le j \le m$)、$m = \lceil \sqrt{p} \rceil$。
$x = i + jm$ ($0 \le i < m$, $0 \le j \le m$)、$m = \lceil \sqrt{p} \rceil$。
2Baby Step
$g^0, g^1, \ldots, g^{m-1}$ をハッシュテーブルに。
$g^0, g^1, \ldots, g^{m-1}$ をハッシュテーブルに。
3Giant Step
$y(g^{-m})^j$ を j を動かして計算、テーブルヒットで答え確定。
$y(g^{-m})^j$ を j を動かして計算、テーブルヒットで答え確定。
4計算量
$O(\sqrt p)$。p=$10^9$ で $m \approx 31623$。
$O(\sqrt p)$。p=$10^9$ で $m \approx 31623$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| x=0 を忘れる | y==1 のケース | if y==1: return 0 |
| 逆元の計算 | g=0 や非互素 | フェルマー小定理は p 素数のみ |
| m の範囲 | j=m まで | range(m+1) |
次のステップ
- Pohlig-Hellman アルゴリズム