\(x\) 回の行動で玉座に座れることと、\(S+xK \equiv 0 \bmod N\) が成り立つことは同値です。

よって「\(Ax \equiv B \bmod M\) となる最小の \(x\) を求めよ」という形の問題が解ければよいです。この問題は次のように解くことができます。

1. \(d=\gcd(A,B,M)\) とし、\(A,B,M\) をそれぞれ \(A/d,B/d,M/d\) に置き換える。
2. \(\gcd(A,M) \neq 1\) のとき解なし
3. \(\gcd(A,M) = 1\) のとき、\(\bmod M\) における \(A\) の逆元を \(A^{-1}\) として、\(x=A^{-1}B\) が解

\(\bmod M\) における逆元は拡張ユークリッドの互除法などを用いて求めることができます。（\(M\) が素数でない場合、\(A^{M-2}\) が \(A\) の逆元になるとは限らないことに注意してください）