2013S_1：转圈游戏

信息学奥赛历年真题 2014年以前NOIP提高组真题 2013S_1：转圈游戏

洛谷：P1965
OJ：P5972

纯模拟，90分

/**************************************************************** 
 * 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*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。

代码实现：

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

代码实现：

/**************************************************************** 
 * 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;
}

Previous Topic

Back to Lesson

Next Topic