[NOIP2013-提高]转圈游戏

GitHub跳转原题关系图返回列表

每轮所有人整体顺时针平移 m 格，10^k 轮后位置为 (x + m·10^k) mod n；只需 10^k mod n，用快速幂在 O(log k) 内求出。

OJ: roj

题目 ID: 3608

难度:普及-

标签:快速幂数学取模python

创建: 2026-10-02 10:17

更新: 2026-10-07 13:50

前置题目
roj 1083计算星期几B 直接复用 A 教的取模快速幂：A 用边乘边取模求 a^b mod 7，B 用同一算法求 10^k mod n 再算 (x+m·10^k) mod n，只是多加了环上位移可叠加的观察

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

nn 个小伙伴编号 0∼n−10 \sim n-1 顺时针围坐一圈，初始 ii 号小伙伴在 ii 号位置。每一轮所有人同时顺时针平移 mm 格，共进行 10k10^k 轮，求 xx 号小伙伴最终所在的位置编号。输入一行四个整数 n,m,k,xn, m, k, x，输出一个整数表示位置。数据范围：0<n<1060 < n < 10^6，0<m<n0 < m < n，1⩽x<n1 \leqslant x < n，0<k<1090 < k < 10^9。样例输入 10 3 4 5，输出 5。

思路

每轮所有人整体平移 mm 格，所以 10k10^k 轮后位置为 (x+m⋅10k) mod n(x + m \cdot 10^k) \bmod n；位置只在 0∼n−10 \sim n-1 之间循环，因此只需 10k mod n10^k \bmod n，用快速幂在 O(log⁡k)O(\log k) 内求出即可。

参考代码

Python 版：

python
import sys

data = iter(map(int, sys.stdin.buffer.read().split()))
n, m, k, x = next(data), next(data), next(data), next(data)
# 每轮所有人整体顺时针移动 m 格 => k 轮共移动 m*10^k 格（mod n）
# pow(10, k, n) 用快速幂求 10^k mod n，O(log k)
print((x + m * pow(10, k, n)) % n)

C++ 版（同一算法）：

cpp
/**
 * 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 15:06
 * update_at: 2026-10-06 15:06
 */
#include <cstdio>

typedef long long ll;

// 快速幂：求 base^exp mod mod，指数按二进制拆分，每次底数平方、指数减半，O(log exp)
ll fast_pow(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() {
    ll n, m, k, x;
    scanf("%lld%lld%lld%lld", &n, &m, &k, &x);
    // 每轮所有人整体顺时针平移 m 格，10^k 轮共平移 m*10^k 格
    // 位置只在 0..n-1 循环，故只需 10^k mod n
    ll step = fast_pow(10, k, n);
    printf("%lld\n", (x + m * step) % n);
    return 0;
}