转圈游戏

题目描述

$n$ 个小伙伴（编号 $0\sim n-1$ ）围坐一圈， $i$ 号小伙伴初始在第 $i$ 号位置。每轮位置 $i$ 上的人顺时针走到位置 $(i+m) \bmod n$ ，共进行 $10^k$ 轮，求 $x$ 号小伙伴最后的位置。输入一行四个整数 $n,m,k,x$ ，输出一行一个整数表示答案，数据范围 $1<n<10^6$ ， $0<m<n$ ， $0<k<10^9$ 。样例输入 10 3 4 5，输出 5。

思路

每轮所有人做的事情相同：位置编号 $+m \pmod n$ ，所以 $10^k$ 轮后的位置为 $(x+m\cdot 10^k)\bmod n$ 。用快速幂求出 $10^k \bmod n$ （ $O(\log k)$ ），再代入取模即可，注意用 long long。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9"""转圈游戏：每轮所有人位置顺时针平移 m，共 10^k 轮。"""
import sys

def main() -> None:
    n, m, k, x = map(int, sys.stdin.read().split())
    # 每轮位置编号 +m (mod n)，10^k 轮即快速幂求 m * 10^k mod n
    print((x + m * pow(10, k, n)) % n)

main()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:04
 * update_at: 2026-10-06 01:04
 */

#include <iostream>
using namespace std;

typedef long long ll;

ll n, m, k, x; // n 个位置、每轮平移 m、轮数为 10^k、询问 x 号小伙伴

// 快速幂：返回 base^exp mod mod，中间乘积用 ll 不会溢出。
ll qpow(ll base, ll exp, ll mod) {
    ll result = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) {
            result = result * base % mod;
        }
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k >> x;

    // 每轮全体位置 +m，10^k 轮后位置为 (x + m*10^k) mod n。
    ll ten_pow = qpow(10, k, n);       // 10^k mod n
    ll ans = (x + m * ten_pow) % n;    // 平移总量 m*10^k 对 n 取模
    cout << ans << '\n';

    return 0;
}

目录

题目描述

思路

参考代码