2013S_1：转圈游戏

洛谷：P1965
OJ：P5972

纯模拟，90分

 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
/**************************************************************** 
 * Description: 2013年提高组第一题  转圈游戏 90分
 * Author: Alex Li
 * Date: 2024-10-11 12:04:53
 * LastEditTime: 2024-10-11 12:08:18
****************************************************************/
#include <iostream>
using namespace std;

int n, m, k, x;
int a[1000005];

int main(){
    // 读取输入的四个整数 n、m、k、x
    cin >> n >> m >> k >> x;

    int i=0;
    a[0] = x; // 记录初始位置

    // 模拟小伙伴的位置变化，直到出现循环
    while(1) {
        x += m;        // 小伙伴向前移动 m 个位置
        if (x >= n)    // 如果超过了最大位置编号，循环回到起点
            x -= n;
        i++;
        a[i] = x;      // 记录当前位置
    if (x == a[0]) // 如果当前位置等于初始位置，说明出现循环
       break;
    }
   
    int q = 1;
    // 计算 q = (10^k) % i，其中 i 是循环节的长度
    for (int j = 1; j <= k; j++)
        q = q * 10 % i;

    // 输出经过 10k 轮后 x 号小伙伴所在的位置
    cout << a[q] << endl;

    return 0;
}

快速幂： 100分

根据模运算的的分配率可以得到 (x%n+m%n*10k%n)%n只需用快速幂求出10k

代码解释：

问题理解：

  • 初始状态：有 n 个小伙伴，编号为 0 到 n−1，按顺时针方向围坐一圈。
  • 游戏规则：每一轮中，每个位置的小伙伴都会顺时针移动 m个位置，新的位置为 (当前编号+m)mod  n。
  • 目标：经过 10k 轮后，求编号为 x 的小伙伴所在的位置。

解题思路：

  • 位置变化公式：经过一轮，编号为 x 的小伙伴会移动到位置 (x+m)mod  n。
  • 经过 t 轮后：小伙伴的位置为 (x+m*t)mod  n。
  • 总轮数：t=10k。
  • 问题转化为：计算 final_position=(x+m×10k)mod  n。

代码实现：

  1. 快速幂取模函数 ：
    • 作用：高效计算 10kmod  n。
    • 实现细节：
      • 使用二进制快速幂算法，时间复杂度为 O(log⁡k)。
      • 在每次乘法运算后取模，防止数值过大导致溢出。
  2. 变量定义与输入：
    • 使用 long long 类型：防止数值过大导致的溢出。
    • 读取输入：从标准输入中读取 n、m、k、x。
  3. 计算最终位置：
    • 使用公式： final_position=(x mod  n+(m mod  n)×power_mod mod  n)
  4. 输出结果：
    • 输出 final_position，即编号为 x 的小伙伴经过 10k 轮后所在的位置。

代码实现：

 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
/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-10-11 12:08:22
 * 最后修改: 2025-10-04 22:57:11
 * 文件描述: 2013年提高组第一题  转圈游戏 100分
****************************************************************/
#include <iostream>
using namespace std;


int main() {
    // 定义变量，使用long long防止溢出
    long long n, m, k, x;
    cin >> n >> m >> k >> x;

    // 计算 (10^k) % n，使用快速幂取模
        long long p =1;
        long long base=10;
        while(k>0){
            if(k%2==1){
                p=p*base%n;
            }
            base=base*base%n;
            k/=2;
        }

    // 计算最终位置，final_position = (x + m * (10^k % n)) % n
    long long final_position = (x + m * p) % n;
    // 输出结果
    cout << final_position << endl;

    return 0;
}
Previous Topic
Back to Lesson
Next Topic