1. 约瑟夫环到底在考什么：先读懂 Counting Out

约瑟夫环（Josephus problem）是算法竞赛里最经典的“知道结论很简单，不知道结论死活写不对”的题型。OJ 上的 HDU1457 Counting Out 就是这类题的代表。它描述的场景很直白：n 个人围成一圈，编号从 1 到 n，从某个人开始报数，报到 m 的人出圈，下一个人接着从 1 报数，直到只剩最后一个人，让你输出这个人的编号，有时候还要求输出完整出圈顺序。看起来就是按规则一步步模拟，但数据一大，纯模拟就扛不住了。

这道题适合正在刷 OJ 的新手，也适合准备面试想快速复习基础算法的求职者，更适合那些背过约瑟夫递推公式但一直没搞懂“公式怎么来的”的同学。我的看法是：公式背下来不难，真正值钱的是推导过程。因为算法题里的约瑟夫环经常换皮，换起点、换报数规则、换淘汰节奏，你死记的公式会立刻失效，只有理解了原理才能每次都在几分钟内写出正确的代码。

1.1 这类题目的常见输入形态

从我刷题的实际情况看，HDU1457 这类题的输入通常不止一组数据。常见写法有两种：一种是每行给两个整数 n 和 m，读到 0 0 结束；另一种是用 EOF 作为结束标记，也就是一直读直到文件末尾。这两种写法在代码上的处理不一样：用 0 0 结束，要在循环里先判断读进来的值；用 EOF 结束，则要看 scanf 的返回值是不是 2。

还有一个特别容易忽略的点：编号到底是从 0 到 n-1，还是从 1 到 n。很多教科书和网上的题解推导公式时都默认用 0-based（编号 0 到 n-1），提交前忘了把结果加 1，就会卡在 Wrong Answer 上找不到原因。我拿到一道约瑟夫题，第一件事就是把这几个要素写在草稿纸上：编号从几开始、报数从谁开始、结束标记是什么、n 的范围有多大。别看都是小事，每一条都直接影响代码怎么写。

1.2 动手前先想清楚三个问题

第一个问题：n 的上限是多少。如果 n 只有几千，用数组模拟轻轻松松；如果 n 到了十万甚至百万，模拟法基本必超时，必须走 O(n) 的递推。第二个问题：题目要的是“最后一个幸存者”还是“完整出圈顺序”。只要幸存者，O(n) 递推一行搞定；要完整出圈顺序，就得用链表或者树状数组，复杂度完全不是一个量级。第三个问题：这一轮的报数值 m 是固定的，还是每一轮都会变。变步长的版本我后面单独讲，它的递推公式只是把常数 m 换成一个序列。

这三个问题想清楚，整个解题方向就定了。下面我先把最主流的两种解法摆出来对比一下。

2. 两种解法选型：模拟法 vs 递推法

2.1 模拟法：写起来爽，跑起来慢

最直观的思路就是老老实实模拟：开一个标记数组记录每个人是否还活着，或者干脆建一个循环链表，每一轮走 m 步淘汰一个人。这种方式最贴近生活经验，写的时候不容易理解错题意，但代价是时间复杂度大约是 O(n*m)。n=100、m=1000 的时候无所谓；一旦 n 上到十万，m 再大一点，循环次数就是十亿量级，多半会超时。

不过模拟法并不是一无是处。我在写递推公式之前，一定先用模拟代码跑几组小数据，把答案记下来当“标准答案”。公式写出后再用小数据对拍，这样能快速发现自己是不是漏掉了边界条件。对拍时你会发现很多细节，比如淘汰掉第 m 个人之后，下一个人应该是谁，这个“指针移动”的顺序一旦搞错，结果就会差很远。

2.2 递推法：把问题缩小到 n-1

递推法的核心观察是：第一轮淘汰了一个人之后，剩下的 n-1 个人仍然围成一圈继续报数。这个 n-1 人问题，和原来的 n 人问题“结构完全相同”，只是每个人的编号整体发生了平移。于是只要知道 n-1 人时的幸存者编号，就能把它映射回 n 人时的编号。这样从 1 个人一直推到 n 个人，总复杂度只有 O(n)，空间 O(1)。

很多人不理解为什么递推公式里有个取模，其实取模就是在做“围成一圈”这件事。编号加完 m 之后可能超过当前人数 n，超过的部分要从头再数，取模就是模拟这个回绕过程。

2.3 复杂度对照表

实际做题时，我的选型原则很简单：只要题问的是“最后剩下谁”，一律用递推；只要题问的是“完整出圈顺序”，先看 n，n 小用链表，n 大上树状数组。下面把最关键的递推公式推导过程完整讲一遍。

3. 递推公式推导：为什么是 (f(n-1)+m)%n

3.1 从 0-based 编号开始推导

先把 n 个人编号为 0 到 n-1，并假设从编号 0 的人开始报数，报到 m 的人出圈。设 f(n) 表示这种情况下最后幸存者的编号。显然，只有 1 个人的时候，幸存者就是他本身，所以 f(1)=0。

现在看 n 个人的情况。第一轮，第一个出圈的人是编号 (m-1) mod n 的人。他出圈之后，下一个人开始报数，这个人的编号是 m mod n。剩下 n-1 个人，如果把他们重新编号为 0 到 n-2，就变成了一个规模为 n-1 的约瑟夫环。在这个新环里，幸存者的“新编号”就是 f(n-1)。要把这个新编号映射回原来的编号，只需要加上 m 再对 n 取模，因为整个环形结构相当于整体平移了 m 个位置。

所以递推式就是：

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

注意这里的 m 不用先对 n 取余，因为外面还有一个 % n，最终结果一定是合法的。但写代码时要注意 m 和 n 相乘、相加过程中可能溢出，该用 long long 就大胆用。

3.2 用手算验证公式

拿 n=5、m=3 来验证。按游戏规则走一遍：1 到 5 围成一圈，从 1 开始报数，报到 3 的人出圈。第一轮出圈的是 3；剩下 4、5、1、2，从 4 开始报到 3，出圈的是 1；剩下 2、4、5，从 2 开始，出圈的是 5；剩下 2、4，从 2 开始，报到 3 时又数回 2，于是出圈的是 2，最后幸存者是 4。

再用递推公式算一遍：f(1)=0；f(2)=(0+3)%2=1；f(3)=(1+3)%3=1；f(4)=(1+3)%4=0；f(5)=(0+3)%5=3。0-based 答案是 3，转成 1-based 就是 4，和模拟结果完全一致。这个例子说明，只要编号规则对应得上，公式可以直接在手算时用来做校验。

3.3 三个容易翻车的边界

第一个边界是 m=1。每轮淘汰的都是当前开始报数的那个人，最后一定剩下编号最大的那个人，1-based 答案就是 n。公式推起来也没问题，但单独特判会省一点时间，也避免你多想。

第二个边界是 n=1。直接返回 0（0-based）即可，别让循环进去又退出来，容易出错。

第三个边界是报数起点偏移。如果题目说的是“从编号 k 的人开始报数”，就不能直接套公式的答案。假设 f(n) 是从编号 0 开始报数的结果，那么从 1-based 的 k 开始报数时，0-based 幸存在原编号中是 (f(n)+k-1) % n，再转成 1-based 就是 ((f(n)+k-1)%n) + 1。这个偏移处理我在做变体题时经常用到。

4. 代码实现与提交排坑

4.1 固定 m 的标准 C 解法

递推公式的代码简洁到让人怀疑是不是少写了好多东西，但它确实就是这几行：

#include <stdio.h> int main() { int n, m; while (scanf("%d%d", &n, &m) == 2 && (n || m)) { int s = 0; // f(1) = 0，0-based for (int i = 2; i <= n; i++) { s = (s + m) % i; } printf("%d\n", s + 1); // 转成 1-based } return 0; }

循环里 i 从 2 增长到 n，每一步 s 都变成 i 人时的答案。这个写法有两个关键细节：一是 s 的初值对应 f(1)，所以循环从 2 开始；二是输出前加 1。很多 WA 就是因为这两点没想明白。

如果题目的结束标记不是 0 0，而是直接多组读到 EOF，就把 while 条件改成while (scanf("%d%d", &n, &m) == 2)。如果 m 可能很大，建议把 n、m、s 都声明成 long long，防止中间步骤溢出。有人觉得 n 的范围看着不大就不加 long long，结果 m 给到 1e9，s+m 直接爆掉 int，这种翻车我见过太多次了。

4.2 多组输入与输出格式的坑

老题对输出格式要求很严格，常见的坑有两个。一个是“Case”前缀，有的题要求每组输出前带Case 1:，不对齐就是 Presentation Error。另一个是每组输出之间有没有空行，这个要盯着题目样例看，不能拍脑袋。

读入方面，如果用 0 0 作为结束标记，注意在循环开头就把两个值读进来再判断，不要在循环里又 scanf 一次。我见过有人写成先读 n，判断 n 为 0 break，再读 m，结果 n=0 m=5 这种非法组合直接导致后续数据错位。正确做法是while (scanf("%d%d", &n, &m) == 2 && (n || m))，一口气处理完。

4.3 报数 m 每轮变化的变体

HDU1457 有些版本会给出一个报数序列，第 i 轮用第 i 个报数值。这种情况递推公式依然成立，只要把常数 m 换成对应的序列值。假设当圈里还剩 i 个人时，这一轮使用的报数值存在数组 a[i] 里，代码就是：

long long s = 0; for (int i = 2; i <= n; i++) { s = (s + a[i]) % i; } printf("%lld\n", s + 1);

需要注意的是，a[i] 的下标含义要和“剩下 i 个人”对应上。有的题从剩余 n 个人开始给第一个报数值，有的题给的是从 1 到 n 的一整串数，读入后要确认清楚。我在写这种版本时，习惯先用 n=5 手算一组，再拿代码跑一遍比对，比直接提交探雷靠谱得多。

5. 进阶变体：出圈顺序、超大 n、变步长报数

5.1 要求输出完整出圈顺序时怎么办

只求幸存者，递推是最好的。但有的题目会问完整出圈顺序，这时递推就无能为力了。n 比较小的时候，我直接用 C++ 的 list 写循环链表模拟，代码短、思路清晰：

#include <bits/stdc++.h> using namespace std; int main() { int n, m; while (cin >> n >> m && (n || m)) { list<int> L; for (int i = 1; i <= n; i++) L.push_back(i); auto it = L.begin(); while (!L.empty()) { int step = (m - 1) % (int)L.size(); for (int i = 0; i < step; i++) { ++it; if (it == L.end()) it = L.begin(); } cout << *it; it = L.erase(it); if (it == L.end()) it = L.begin(); cout << (!L.empty() ? ' ' : '\n'); } } return 0; }

这里的 step 先对 L.size() 取余，是为了避免 m 大于当前人数时白转好几圈。erase 返回的是被删元素的下一个元素的迭代器，这个特性能让代码很干净。如果 n 很大，链表模拟会超时，那就得换树状数组维护“还剩多少人”，配合二分查找第 k 个存活者，做到 O(n log n)。

5.2 n 超大而 m 很小时的批量跳步优化

有一种极端情况：n 高达 1e9 甚至 1e18，m 却很小，比如 m=2 或 m=3。这时候 O(n) 的递推也太慢，需要批量跳步。原理是：当 s + m 小于当前人数 i 时，取模不会生效，s 只是简单地加上 m，这个“线性增长”阶段可以连续跳过很多轮。

long long josephus_large(long long n, long long m) { if (m == 1) return n - 1; long long s = 0; long long i = 2; while (i <= n) { if (s + m < i) { // 连续跳 step 轮，期间不需要取模 long long step = (i - 1 - s + m - 2) / (m - 1) - 1; long long remain = n - i + 1; if (step > remain) step = remain; s += step * m; i += step; } else { s = (s + m) % i; i++; } } return s; }

这个优化建议配合小数据对拍吃透，否则公式里的除法边界容易写错。我自己验证过 n=100、m=2 时它给出的答案是 72（0-based），和经典结论一致。但这类优化题在 HDU1457 里大概率用不上，当作扩展知识了解即可。

5.3 把递推推广到变步长报数

变步长报数的思路和固定 m 一样，只是公式里的 m 变成序列。假如题目给了长度为 n 的数组，第 i 个元素表示当圈里剩余 i 个人时，从 1 数到这个数淘汰，那么答案就是s = (s + a[i]) % i从 i=2 推到 n。这里有个容易混的点：数组顺序是从剩余人数多到少，还是从少到多？要按“剩余 i 个人”来组织才会和递推方向一致。

这种变体在面试题里偶尔出现，核心还是考察你有没有真正理解递推公式的推导过程。能讲清楚“为什么偏移量是 m”而不是背下来，这类题就都难不住你。

6. 常见问题与排查速查表

6.1 高频踩坑点

我自己这些年刷题、写题解，发现约瑟夫环的 WA 几乎都集中在下面这些地方：

6.2 对拍与调试技巧

我强烈建议在正式提交前写一个暴力模拟版本，随机生成小数据，把模拟答案和递推答案逐组对比。这个方法看起来笨，但排查边界条件特别快。比如 n=1、m=100 这种组合，模拟代码可能根本没写到，递推公式也可能因为 m 和 n 的关系出问题，对拍一两次就能抓出来。

另一种实用调试法是手算小数据。n=5、m=3 的结果是 4，n=7、m=2 的结果是 7，这几个固定组合可以作为“记忆测试点”。如果代码在这几组上全对，正确率就很有保障了。

7. 刷题之外的一点心得

约瑟夫环这类题给我的最大体会是：算法的价值不在于你背了多少模板，而在于你能不能把一个动态过程抽象成一个递推关系。第一次学递推公式时，我也觉得“这怎么可能一步到位”，直到自己从 n=5 一步步推到 n=6，才真正理解取模的意义。后来遇到变步长、变起点、输出完整顺序，都能顺着这个思路快速写出来。

最后分享一个小技巧：不管题目给的编号是 1 还是 0，我在草稿上一律先用 0-based 推，推完再统一转换。这样可以避免在推导过程中反复纠结号，思路会清晰很多。你可以试试看，几次之后你会发现所有约瑟夫环变体题，本质上都是同一个公式在换皮。