题目分析

本题是一个循环移位问题。$n$ 个小伙伴围成一圈，每轮所有小伙伴顺时针移动 $m$ 个位置，经过 $10^k$ 轮后，求编号为 $x$ 的小伙伴所在的位置。

数学建模

设初始时位置 $i$ 上的小伙伴编号为 $i$。

经过 $1$ 轮后，位置 $i$ 上的小伙伴编号为：

经过 $t$ 轮后，位置 $i$ 上的小伙伴编号为：

我们要求的是经过 $10^k$ 轮后，编号为 $x$ 的小伙伴在哪个位置 $p$，即解方程：

解得：

核心算法

因此问题转化为计算：

由于 $k$ 最大可达 $10^9$，直接计算 $10^k$ 会溢出，需要使用快速幂算法计算 $10^k \bmod n$。

代码解析

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

long long n, k, x, m;

int main() {
    cin >> n >> m >> k >> x;
    
    int anss = 10, ans = 1;  // anss 是底数，ans 是结果
    
    // 快速幂计算 10^k mod n
    while (k != 0) {
        if (k & 1)  // 如果当前位为1
            ans = (ans * anss) % n;
        
        anss = (anss * anss) % n;  // 底数平方
        k >>= 1;  // 指数右移
    }
    
    // 计算最终位置
    cout << (x + m * ans) % n << endl;
    
    return 0;
}

算法步骤

1. 输入：读取 $n$, $m$, $k$, $x$
2. 快速幂计算 $10^k \bmod n$：
   • 初始化 anss = 10（底数），ans = 1（结果）
   • 遍历 $k$ 的二进制位：
     • 如果当前位为 $1$：ans = (ans * anss) % n
     • 平方底数：anss = (anss * anss) % n
     • 右移指数：k >>= 1
3. 计算最终位置：$p = (x + m \cdot \text{ans}) \bmod n$
4. 输出：位置 $p$

复杂度分析

• 时间复杂度：$O(\log k)$
  • 快速幂的循环次数为 $k$ 的二进制位数
  • 对于 $k \leq 10^9$，最多循环约 $30$ 次
• 空间复杂度：$O(1)$
  • 只使用了常数个变量

示例验证

对于样例输入：

n=10, m=3, k=4, x=5

计算过程：

1. 计算 $10^4 \bmod 10 = 0$
   • $k=4$ 的二进制：$100$
   • 循环过程：
     • $k=4$：anss=10 → anss=(10*10)%10=0
     • $k=2$：anss=(0*0)%10=0
     • $k=1$：ans=(1*0)%10=0，anss=(0*0)%10=0
2. 计算位置：$p = (5 + 3 \times 0) \bmod 10 = 5$

输出：5，与样例一致。

关键点说明

• 模运算性质：$(a \cdot b) \bmod n = [(a \bmod n) \cdot (b \bmod n)] \bmod n$
• 快速幂原理：将指数 $k$ 用二进制表示，通过平方和乘法分解计算
• 循环移位等价性：顺时针移动 $m$ 格等价于逆时针移动 $n-m$ 格，但本题采用数学推导直接得出公式

该算法能够高效处理 $k$ 高达 $10^9$ 的大数据范围，是本题的最优解法。