No.042 D

まず, フェルマーの小定理から $A, B$ 間に $P-1$ の倍数が含まれている場合は最小値は $1$ になる. 以後 $A, B$ は $P-1$ の剰余を取っておく.

$B-A$ が小さいときは愚直にすべて試す.

$B-A$ が大きいときは, 入力がランダムなので答えも小さい可能性が高い. よって, 小さい $k$ から順に

$$X^i \equiv k \pmod{P}$$

となる $i$ が $A, B$ 間に含まれているかどうかを調べる.

このような $i$ を求める方法として, Baby-step Giant-step アルゴリズムを用いる.

これは $M = \lceil \sqrt{P} \rceil$ とおき, $X^{iM-j} \equiv k$ となる $i, j$ ($0 \lt i \leq M, 0 \leq j \lt M$) を求めるやり方である.

$X^{iM-j} \equiv k$ から $X^{iM} \equiv kX^j$ となる. $kX^j$ をすべての $j$ について求めてソートしておき, $X^{iM}$ がその中に含まれるかどうかを二分探索で求める.