/**************************************************************** 
 * 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*10^k%n)%n只需用快速幂求出10^k

代码解释：

问题理解：

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

解题思路：

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

代码实现：

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

代码实现：

/**************************************************************** 
 * 代码作者: 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