1617：转圈游戏

题目描述

$n$ 个小伙伴（编号从 $0$ 到 $n-1$）围坐一圈玩游戏。按照顺时针方向给 $n$ 个位置编号，从 $0$ 到 $n-1$。最初，第 $0$ 号小伙伴在第 $0$ 号位置，第 $1$ 号小伙伴在第 $1$ 号位置，……，依此类推。

游戏规则如下：每一轮第 $0$ 号位置上的小伙伴顺时针走到第 $m$ 号位置，第 $1$ 号位置小伙伴走到第 $m+1$ 号位置，……，依此类推，第 $n-m$ 号位置上的小伙伴走到第 $0$ 号位置，第 $n-m+1$ 号位置上的小伙伴走到第 $1$ 号位置，……，第 $n-1$ 号位置上的小伙伴顺时针走到第 $m-1$ 号位置。

现在，一共进行了 $10^k$ 轮，请问 $x$ 号小伙伴最后走到了第几号位置。

输入格式

输入共 $1$ 行，包含 $4$ 个整数 $n、m、k、x$，每两个整数之间用一个空格隔开。

输出格式

输出共 $1$ 行，包含 $1$ 个整数，表示 $10^k$ 轮后 $x$ 号小伙伴所在的位置编号。

样例

样例输入 #1

10 3 4 5

样例输出 #1

5

样例解释 #1

• $n=10$ 个小伙伴，每轮移动 $m=3$ 个位置，进行 $10^k = 10^4 = 10000$ 轮，询问 $x=5$ 号小伙伴最终位置。
• 初始时，小伙伴编号与位置编号相同，即小伙伴 $5$ 在位置 $5$。
• 每轮移动相当于所有小伙伴的位置编号增加 $m$ 并对 $n$ 取模。
• 经过 $t$ 轮后，位置编号变为 $(初始位置 + m \times t) \bmod n$。
• 所以 $x$ 号小伙伴最终位置为 $(x + m \times 10^k) \bmod n$。
• 计算：$10^4 = 10000$，$m \times 10^k = 3 \times 10000 = 30000$，$30000 \bmod 10 = 0$，所以 $(5 + 0) \bmod 10 = 5$。
• 输出 $5$。

数据范围

• 对于 $30\%$ 的数据，$0 < k < 7$
• 对于 $80\%$ 的数据，$0 < k < 10^7$
• 对于 $100\%$ 的数据，$1 < n < 10^6$，$0 < m < n$，$1 \le x \le n$，$0 < k < 10^9$

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题的关键是计算 $m \times 10^k \bmod n$。由于 $k$ 可能很大，不能直接计算 $10^k$，需要用快速幂计算 $10^k \bmod n$，然后乘以 $m$ 再取模。注意 $n$ 不是质数，但快速幂取模仍然适用。最终答案为 $(x + m \times 10^k \bmod n) \bmod n$。由于 $x$ 在 $[1, n]$ 范围内，而位置编号从 $0$ 开始，但题目说 $x$ 号小伙伴初始在位置 $x$，说明位置编号也是从 $1$ 开始？实际上题目描述：编号从 $0$ 到 $n-1$，最初第 $0$ 号小伙伴在第 $0$ 号位置，所以位置编号也是 $0 \sim n-1$。但输入 $x$ 的范围是 $1 \le x \le n$，可能 $x=n$ 对应编号 $0$？需要仔细理解。根据样例，$n=10, x=5$，输出 $5$，说明 $x$ 就是位置编号，且从 $0$ 开始？但 $x=5$ 在 $[1,10]$ 内，所以 $x$ 可能是 $1 \sim n$，对应位置编号 $x-1$？验证：如果 $x$ 是 $1 \sim n$，初始位置应为 $x-1$，则最终位置为 $(x-1 + m \times 10^k) \bmod n$。样例中 $x=5$，初始位置 $4$，计算 $(4 + 3 \times 10000) \bmod 10 = 4$，输出应为 $4$，但样例输出 $5$，矛盾。所以 $x$ 就是位置编号，且从 $0$ 开始，但输入范围 $1 \le x \le n$ 中，当 $x=n$ 时对应位置 $0$？实际上 $n=10$ 时位置编号为 $0\sim 9$，没有 $10$，所以 $x$ 应为 $0 \sim n-1$，但题目可能输入 $1 \sim n$，需要转换。但样例输入 $x=5$ 输出 $5$，说明 $x$ 就是位置编号 $5$。因此我们直接使用 $x$ 计算即可，注意 $x$ 可能等于 $n$？如果 $x=n$，则位置编号为 $0$（因为模 $n$ 后为 $0$）。所以最终公式为 $(x \bmod n + m \times 10^k \bmod n) \bmod n$，其中 $x$ 是输入的 $x$。为保险起见，可以先将 $x$ 对 $n$ 取模。