公式解説と同様の方針で、\(O\left(\sqrt{M}\right)\) 時間を達成する方法をご紹介します。

公式解説の方針で \(O(\log M)\) 時間の寄与は次の計算です:

\[ x^i \ ( 0 \le i \lt M ) \\ \sum_{j=0}^{i-1} y^j \ ( 0 \le i \lt M ) \]

（ただし \(y = x^h\)）

これは \(k \sim \sqrt{M}\) として、\(i \sim \sqrt{M}\) 程度まで

\[ x ^ i, \ x ^ {ik} \\ \sum_{j = 0}^{i - 1} y^j , y^{ik}, \sum_{j = 0}^{i - 1} y^{jk} \\ \]

を前計算しておくと計算でき、\(\langle O(\sqrt{M}), O(1) \rangle\) 時間を達成できます。