公式解説のBaby step Giant stepとほぼ同等ですが、行列を使った解法を紹介します。

以下、mod pで議論します。

\[ X_{i+1} = aX_i+b \]

は以下のようなアフィン変換として表現できます。

\[ \begin{pmatrix} X_{i+1} \\ 1 \\ \end{pmatrix} = \begin{pmatrix} a & b \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} X_i \\ 1\\ \end{pmatrix} \]

ここで、\(\begin{pmatrix} a & b \\ 0 & 1 \\ \end{pmatrix}\)を\(A\)とおくと、問題は

\[ \begin{pmatrix} g \\ 1 \\ \end{pmatrix} = A^k \begin{pmatrix} s \\ 1\\ \end{pmatrix} \]

を満たす最小の\(k\)を求めよ、といいかえることができます。 ここで、\(\sqrt{p}=r\)と置いた時に、\(r\)以下の整数\(n\)と\(m\)を用いて，

\[ \begin{pmatrix} g \\ 1 \\ \end{pmatrix} = A^{nr+m} \begin{pmatrix} s \\ 1\\ \end{pmatrix} \]

とできます。 さらに、

\[ (A^{-1})^{nr} \begin{pmatrix} g \\ 1 \\ \end{pmatrix} = A^{m} \begin{pmatrix} s \\ 1\\ \end{pmatrix} \]

とできます。ここで、\(A^{-1}\)はAの逆行列で、

\[ \begin{pmatrix} 1 & -b/a \\ 0 & 1/a \\ \end{pmatrix} \]

と求めることができます。 \(a=0\)の時は逆行列は存在せず、別に求める必要があります。(公式解説参照)

\(a>0\)の場合は、\(m ∈ [0, sq]\)、\(n ∈ [0, sq]\)について、 baby step giant stepを行います。

具体的には、全てのmについて \(A^{m} \begin{pmatrix} s \\ 1\\ \end{pmatrix} \)を前計算して、Hash mapに登録します。 そして、\( (A^{-1})^{nr} \begin{pmatrix} g \\ 1 \\ \end{pmatrix} \)をn=0, 1, …と計算していき、\(A^{m} \begin{pmatrix} s \\ 1\\ \end{pmatrix} \)の中に結果が一致するものがあれば、その時の\(nr+m\)が解となります。どれとも一致しなければ、-1を出力します。

実装例(Rust) https://atcoder.jp/contests/abc270/submissions/35160312