题解：P1965 [NOIP2013 提高组] 转圈游戏

AFO_kunkun127 · 2025-01-08 13:52:43 · 题解

思路

此题根据题意模拟即可。

由于是 n 个人在转圈，每个人每次前进 m 个单位，走 10^k 次。

显然，每个人移动过 n 个单位后回到起点，相当于没运动，因此我们可以直接计算初始位置 x 加上 10^k m，再对一圈的长度 n 取模即可求出答案。

注意事项

• 计算 10^k 时数据较大，要用快速幂。
• 编号从 0 开始。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL ksm(LL a, LL b, LL p)
{
    LL ans = 1;
    while (b)
    {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

int main()
{
    int n, m, k, x;
    cin >> n >> m >> k >> x;
    cout << (x % n + m % n * ksm(10, k, n) % n) % n << endl;
    return 0;
}