P1965 [NOIP 2013 Senior] Circle Game

NOIP 2013 Senior D1T1.

$n$ friends (numbered from $0$ to $n-1$) sit in a circle to play a game. The $n$ positions are numbered clockwise from $0$ to $n-1$. Initially, friend $0$ is at position $0$, friend $1$ is at position $1$, and so on. The rules are as follows: in each round, the friend at position $0$ moves clockwise to position $m$, the friend at position $1$ moves to position $m+1$, and so on; the friend at position $n-m$ moves to position $0$, the friend at position $n-m+1$ moves to position $1$, ... , and the friend at position $n-1$ moves clockwise to position $m-1$. Now, after a total of ${10}^k$ rounds, determine which position friend $x$ ends up at.

One line containing four integers $n, m, k, x$, with a single space separating each pair of integers.

One integer, the position index where friend $x$ is located after ${10}^k$ rounds.

For $30\%$ of the testdata, $0 < k < 7$. For $80\%$ of the testdata, $0 < k < {10}^7$. For $100\%$ of the testdata, $1 < n < {10}^6$, $0 < m < n$, $0 \le x \le n$, $0 < k < {10}^9$. Translated by ChatGPT 5