For ABC E - Throne, which says the following: We have N chairs arranged in a circle, one of which is a throne.
Takahashi is initially sitting on the chair that is S chairs away from the throne in the clockwise direction. Now, he will repeat the move below.
Move: Go to the chair that is K chairs away from the chair he is currently sitting on in the clockwise direction.
After how many moves will he be sitting on the throne for the first time? If he is never going to sit on it, report -1 instead.
The solution says, He can sit on the throne after x moves if and only if S + x K ≡ 0 mod N. Why is this true?
Number the chairs from $0$ to $N-1$ in the clockwise order. Assume that chair $0$ is the throne. This means that Takahashi sits on chair $S$ initially. Now, he moves to the chair that is $K$ chairs away in the clockwise direction. So the chair number would be $S+K$, but if this number goes past $N-1$ we should only look at the remainder when $S+K$ is divided by $N$(this is the essence of modular arithmetic where we wrap around the numbers in a circle). This means that in the first move, his position will be $S+K\pmod N$. In the second move, it will be $S+2K\pmod N$. His position after $x$ moves will be $S+xK\pmod N$.
Since chair numbered $0$ is the throne, he sits on it after $x$ moves if and only if $S+xK\equiv 0\pmod N$. The smallest $x$ for which this holds gives you the number of moves when he'll sit on the throne for the first time.