🧩 题目题解：移除石子游戏（Josephus 环问题变形）

✅ 题目概述

题目描述了一个石子移除的游戏：

• $n$ 块石子围成一圈，编号 $1$ 到 $n$。
• 初始移除编号为 $m$ 的石子；
• 之后每次从上一次移除的石子位置出发，顺时针跳过 $k - 1$ 个仍然存在的石子，移除下一个；
• 重复直到只剩一块石子，输出它的编号。

🧠 题目分析

这个问题实际上是 约瑟夫环（Josephus Problem） 的一个变种：

• 原始 Josephus 问题是每隔 $k$ 人杀一个，问最后剩下谁；
• 本题略有不同：第一次移除编号为 $m$ 的人，从该位置出发，之后按 Josephus 规则循环执行；
• 最后输出的是该“生还者”的原始编号（注意是 $1$~$n$ 编号，而不是数组下标）。

⚙️ 算法思路

Josephus 问题公式：

设 f(n) 为 $n$ 个人时，最终剩下的人的下标（从 $0$ 开始编号），有递推关系：

f(1) = 0
f(n) = (f(n-1) + k) % n

本题在此基础上：

• 从 $2$ 人开始递推（因为第一步移除了 $1$ 人）；
• 最终结果是从编号 $m$ 的石子开始数，所以最后将 Josephus 值偏移 $m$，并映射回 $1$~$n$ 的编号范围。

🔢 完整代码 + 注释

#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
    int n, m, k;
    // 多组测试数据，直到读入 0 0 0 结束
    while (~scanf("%d%d%d", &n, &k, &m), m || k || n)
    {
        int s = 0; // Josephus 编号（从 0 开始）
        for (int i = 2; i <= n - 1; i++)
            s = (s + k) % i; // 递推公式，找出最后剩下的人的下标（去掉初始移除的一个）

        printf("%d\n", (s + m) % n + 1); // 偏移 m 作为起点，映射到 1~n 范围
    }
    return 0;
}

📌 复杂度分析

• 时间复杂度：每组测试是 $O(n)$，最多 $10^4$；
• 空间复杂度：$O(1)$，无需数组存储，利用递推节省空间；
• 代码高效地解决了约瑟夫问题的实际应用变种。

✅ 输入示例

8 5 3
100 9999 98
10000 10000 10000
0 0 0

✅ 输出示例

1
93
2019

💡 总结

这是一道利用经典递推技巧的模拟题，虽然看起来复杂，但通过 Josephus 问题的数学归纳可以大大简化计算，避免使用链表或数组模拟，非常适合用来考察递推与编号映射技巧。