Contest Duration: - (local time) (100 minutes) Back to Home

## E - Throne Editorial by en_translator

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)

posted:
last update: