Sugoroku Game 2

この問題は、以下のように言い換えることができます。

• $S \times K^x \equiv G \pmod N$ となるような最小の非負整数 $x$ を求めてください。

これは、典型的な離散対数問題であり、Baby Step Giant Step と呼ばれるアルゴリズムで $1$ ケースあたり $O(\sqrt{N} \log N)$ で解くことができます。

$S = G$ の場合は明らかに答えが $0$ であり、$K, N$ が互いに素でない場合は答えが $0, 1$ または 到達不可能であるということに注意してください。