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
/**************************************************************** 
 * 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;
    a[0] = x; // 记录初始位置

    // 模拟小伙伴的位置变化,直到出现循环
    for (i = 1;; i++) {
        x += m;        // 小伙伴向前移动 m 个位置
        if (x >= n)    // 如果超过了最大位置编号,循环回到起点
            x -= n;
        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. 快速幂取模函数 mod_pow
    • 作用:高效计算 10kmod  n。
    • 实现细节
      • 使用二进制快速幂算法,时间复杂度为 O(log⁡k)。
      • 在每次乘法运算后取模,防止数值过大导致溢出。
  2. 变量定义与输入
    • 使用 long long 类型:防止数值过大导致的溢出。
    • 读取输入:从标准输入中读取 n、m、k、x。
  3. 计算 10kmod  n
    • 调用 mod_pow(10, k, n),得到 power_mod
  4. 计算最终位置
    • 使用公式: final_position=(x mod  n+(m mod  n)×power_mod mod  n)
    • 步骤解析
      • 先计算 m mod  n 和 x mod  n,保证数值在范围内。
      • 计算 (m mod  n)×power_mod mod  n,防止乘法溢出。
      • 最后将结果加上 x mod  n,再取模 n。
  5. 输出结果
    • 输出 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**************************************************************** 
 * Description: 2013年提高组第一题  转圈游戏 100分
 * Author: Alex Li
 * Date: 2024-10-11 12:07:57
 * LastEditTime: 2024-10-11 12:08:08
****************************************************************/
#include <iostream>
using namespace std;

#define LL long long


// 快速幂取模函数,计算 (base^exponent) % mod
LL mod_pow(LL base, LL exponent, LL mod) {
    LL result = 1;    // 初始化结果为1
    base %= mod;             // 先取模,防止base过大

    while (exponent > 0) {
        // 如果当前指数位是1,则将结果乘以base
        if (exponent & 1)
            result = result * base % mod;
        // base自乘,指数右移一位
        base = base * base % mod;
        exponent >>= 1;
    }
    return result;
}

int main() {
     freopen("circle.in","r",stdin);
     freopen("circle.out","w",stdout);
    // 定义变量,使用long long防止溢出
    LL n, m, k, x;
    cin >> n >> m >> k >> x;

    // 计算 (10^k) % n,使用快速幂取模
    LL power_mod = mod_pow(10, k, n);

    // 计算最终位置
    // final_position = (x + m * (10^k % n)) % n
    LL final_position = (x % n + (m % n) * power_mod % n) % n;

    // 输出结果
    cout << final_position << endl;

    return 0;
}
Scroll to Top