Atcoder Regular Contest 042 D - あまり
問題概要
4整数 X, P, A, B が与えられる．P は素数．$1\leq X < P < 2^{31}$, $0 \leq A \leq B < 2^{31}$. $X^i \,\%\, P$ の $A \leq i \leq B$ での最小値を求めよ．X, P, A, B は乱数で与えられるので，意地悪な入力は来ないと思って良い．
解法
B - A が小さい時には$A\leq i \leq B$なる$i$を全部調べれば良いです．実験してみると $B - A \leq 10^{8}$ くらいまでは全部調べるのは1秒程度でできるようです．
B - A が大きい場合は，$X^{i} \equiv k$ (mod P) となる $A \leq i \leq B$ が存在するかどうか，k = 1, 2, ... と順に調べることにします．乱暴な見積もりですが，$\{X^i \,\%\, P \mid A \leq i \leq B\}$ が，区間 $[0,P)$ で一様に分布するとみなすと，その「濃度」は，$|B-A|/P \geq 10^8/2^{31} \approx 1/20$ です．ですから，k を1から20まで，とは言わずとも1から数百くらいまで調べれば，多分そのような$i$があるだろうと考えます (問題文で実際に提示されている乱数が生成した入力では，最大で34まで調べるとみつかりました)． そこで，各$k$についての判定問題が，そこそこ速く($10^{6}$ステップくらいで) とければ良い，ということになります．．
$k$が与えられて $X^{i} \equiv k$ (mod P) なる $i$ を求めるのは，離散対数問題 (なるほど) といわれていて，比較的効率よく解く方法として，baby-step giant-step なるものがあるのだそうです．以下 Wikipedia の記事 に書いてあることそのままですが:
$0 \leq i < P$ ですから，$m = \lceil\sqrt{P}\,\rceil$ とすると，$i = pm+q$
と書けます．
$X^i \equiv k$ を書き直すと $X^q \equiv k\cdot (X^{-m})^{p}$ となりますので，$X^q$
を前計算しておいて，$X^q$ から $q$ を引けるようにしておけば，
に対して
を計算してはここから$q$が引けるかどうか見ていけば良い．ということで，めでたく $O(\sqrt{P}\log{P})$ で解けました．$X^q$から$q$を引くのが定数時間なら $O(\sqrt{P})$ ですね．
これは平方分割みたいなものですね．$X^i % P$ を順に計算して$k$になるかどうか調べるのでは，最悪 $P$ 回計算しなくてはいけない．しかし，$X^i$ の結果を正方形に並べてみると，各マスの値は，最上行と最左列の積になっている．ということは，最上行の各マスについて，何を掛けたら $k$ になるかをあらかじめ調べておけば，最左列を順にみるだけでできちゃう．
感想
離散対数問題ということも知らなければ，baby-step giant-step ということも知らなかったので，もちろん，解けませんでした．
