He can sit on the throne after \(x\) moves if and only if \(S+xK \equiv 0 \bmod N\).

Therefore, it is sufficient to find “the minimum \(x\) such that \(Ax \equiv B \bmod M\).” This problem can be solved in the following way:

1. Let \(d = \gcd(A,B,M)\), and replace \(A,B,M\) with \(A/d,B/d,M/d\) respectively.
2. If \(\gcd(A,M) \neq 1\), no solution exists.
3. If \(\gcd(A,M) = 1\), \(x=A^{-1}B\) is the solution, where \(A^{-1}\) is the inverse of \(A\) modulo \(M\).

The inverse modulo \(M\) can be calculated with extended Euclidean algorithm. (Note that \(A^{M-2}\) is not necessarily the inverse of \(A\) if \(M\) is not a prime)