如果让我选一道“题目很短、坑很深”的 UVA 老题，我会投 UVa 151 Power Crisis。它看起来就是约瑟夫环：给你 n 个编号区域，找到一个最小的 m，让 13 号区域最后停电。可如果你拿标准约瑟夫递推去套，连样例 n=17 都过不了。原因在于，题面里 1 号区域是固定先停的，之后的“每隔 m 个停一个”才真正开始。这篇文章会把“先拿走 1 号”这个变形讲透，包括递推式的来源、手算 17 的完整过程，以及能直接提交的 C++ 和 Python 代码。
1. 重新读题：这不是标准的“数到 m 被杀”，而是“1 号先出局”
1.1 题面规则里最关键的一行
UVa 151 Power Crisis 的输入很简单：每行一个 n，读到 0 结束。输出是一个 m，要求在这个 m 下，最终停下来时剩下的那个区域编号是 13。
真正的坑在规则描述里。题面并不是让你从 1 号开始数 1、2、3……数到 m 再停掉第 m 个。它说的是：1 号区域第一个被停掉，然后从 2 号区域开始，在仍然供电的区域里继续数 m 个，再停掉第 m 个。也就是说，1 号是“内定”的第一刀，后面才开始做约瑟夫环。
这一行如果漏看，后面全错。我当年就是先写了标准约瑟夫函数，跑样例 17 的时候得到了一个完全不同的数字，先是一脸懵，后来才回去逐字读题。
1.2 标准约瑟夫 vs 本题变体
假设 n=17，m=7。
如果按标准约瑟夫，“从 1 号开始数 7 个，停掉第 7 个”，那么第一刀切在 7 号，递推算下来最后幸存的是 2 号。
如果按本题规则，“1 号先停，然后从 2 号开始数 7 个”，第一刀切完 1 号之后，第二刀会切在 8 号，最终幸存者正好是 13 号。
| 规则 | n=17, m=7 的第一刀 | 最终幸存 |
|---|---|---|
| 标准约瑟夫 | 7 | 2 |
| UVa 151 变体 | 1 | 13 |
所以这个题的解题思路必须从一开始就改成：先把 1 号从环里拿走，再对剩下的 n-1 个节点做约瑟夫问题。
1.3 样例反推：17 对应 7 不是巧合
实际手动模拟 n=17, m=7，按本题规则的停电顺序是：
1 -> 8 -> 15 -> 6 -> 14 -> 7 -> 17 -> 11 -> 5 -> 3 -> 2 -> 4 -> 10 -> 16 -> 9 -> 12
最后剩下 13 号。
这条顺序如果能在草稿纸上推一遍，你对这个题的理解会比直接背代码深很多。注意中间会有跨过结尾继续数的情况，比如数到 17 之后会回到 2、3、4……这也是约瑟夫环最核心的“循环取模”思想。
2. 把区域重新编号：为什么代码里判断的是 11，而不是 13
2.1 拿走 1 号后，剩下的区域是什么
1 号已经先出局，所以剩下的节点是：
2, 3, 4, ..., n
这串节点一共有 n-1 个。如果给它们重新编号，从 0 开始：
- 0 号对应原区域 2
- 1 号对应原区域 3
- 2 号对应原区域 4
- ...
- 11 号对应原区域 13
所以“13 号区域最后幸存”等价于“在新编号里下标 11 幸存”。这个映射关系就是整个代码里== 11的来源。如果这里直接写== 13，哪怕递推式写对了，答案也一定错。
2.2 约瑟夫递推式到底怎么来的
现在的问题变成：有 N = n-1 个节点，按环形排列，每轮从当前位置开始数 m 个，杀掉第 m 个，求最后幸存者的 0 基下标。
设J(i)表示当环里还剩 i 个节点时，最后幸存者在当前环中的下标，0 基。显然：
- i = 1 时，只剩一个人，幸存者下标是 0
- i > 1 时，第一刀会杀到下标
(m-1) % i的位置
杀掉这个位置后，下一轮从它后面的那个节点开始数。如果把剩下的 i-1 个节点重新从 0 编号，那么幸存者的新编号是J(i-1)。把新编号映射回旧编号时，需要加上第一刀后面的偏移，也就是m mod i。
所以：
J(i) = (J(i-1) + m) % i
这个式子不需要死记。你只需要记住：每杀一个人，环的长度减一，但起点往后挪了 m 个位置，取模就是为了处理循环绕圈。
2.3 这里用 n 还是 n-1，是最大的分水岭
很多帖子里的代码写的是：
for (int i = 2; i <= n; ++i) s = (s + m) % i;这是标准约瑟夫，适用范围是“从第 1 个人开始数 m 个然后杀掉”。但本题一开始就强制把 1 号杀了，所以不能直接对 n 个节点套。
正确做法是只对 n-1 个剩余节点做递推：
for (int i = 1; i <= n - 1; ++i) s = (s + m) % i;i从 1 到 n-1，代表剩余节点数逐渐从 1 增长到 n-1。这实际上是在做动态规划式的递推，而不是真的去模拟删除。
3. 手推 n=17：答案为什么是 7
3.1 先看 m=1 到 m=7 的最终结果
因为题目要求最小的 m，所以从 m=1 开始逐层检查。我只列出递推到最后一轮时J(16)的最终值，也就是在新编号下最后幸存者的下标。
| m | J(16) | 对应原区域 |
|---|---|---|
| 1 | 15 | 17 |
| 2 | 0 | 2 |
| 3 | 7 | 9 |
| 4 | 0 | 2 |
| 5 | 5 | 7 |
| 6 | 12 | 14 |
| 7 | 11 | 13 |
可以看到 m=6 的时候其实已经很接近了，最后幸存的是 14 号，就差一位。但 m=7 的时候J(16)=11，对应原区域 13 号，所以最小答案就是 7。
3.2 m=7 的完整递推表
如果你第一次接触这个递推式，可能会觉得它太抽象。我把 m=7 时每一轮的J(i)列出来，你可以对着算一遍：
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| J(i) | 0 | 1 | 2 | 1 | 3 | 4 | 4 | 3 | 1 | 8 | 4 | 11 | 5 | 12 | 4 | 11 |
计算过程就是反复执行：
J(i) = (J(i-1) + 7) % i
例如：
J(12) = (J(11) + 7) % 12 = (4 + 7) % 12 = 11J(13) = (11 + 7) % 13 = 18 % 13 = 5J(16) = (4 + 7) % 16 = 11
最后J(16)=11，映射回原区域就是 13。整个过程一点魔法都没有，就是每一轮更新一下幸存者的相对位置。
4. 能直接提交的 C++ 和 Python 代码
4.1 C++ 版本
这里用最直接的写法，每找到一个 n，就从 m=1 开始往上试。
#include <bits/stdc++.h> using namespace std; int survivorIndex(int n, int m) { // n 是原始区域数 // 1 号已经先停掉，所以只对 n-1 个节点做约瑟夫递推 int s = 0; // 0 基下标：剩下 1 个节点时，幸存者下标是 0 for (int i = 1; i <= n - 1; ++i) { s = (s + m) % i; } return s; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; while (cin >> n && n) { int m = 1; // 目标是新编号里的 11，也就是原区域 13 while (survivorIndex(n, m) != 11) { ++m; } cout << m << '\n'; } return 0; }需要注意for (int i = 1; i <= n - 1; ++i)，这个n - 1是整个解法的关键。如果你写成i <= n，就把 1 号也放进递推里了，样例直接挂。
4.2 Python 版本
Python 在 UVA 老平台上不算快，但 n 的数据范围很小，这个写法完全够用。
import sys def survivor_index(n, m): s = 0 # i 从 1 到 n-1，对应剩余节点数从 1 增长到 n-1 for i in range(1, n): s = (s + m) % i return s def main(): out = [] for line in sys.stdin: n = int(line.strip()) if n == 0: break m = 1 while survivor_index(n, m) != 11: m += 1 out.append(str(m)) sys.stdout.write("\n".join(out)) if __name__ == "__main__": main()Python 的range(1, n)会生成 1 到 n-1，正好对应 C++ 里的循环范围。
4.3 提交前一定要确认的四个边界
- n=13 时，答案应该是 1。因为 1 号先停，然后 2、3、4……12 依次被停，最后剩下 13 号。
- n=14 时，答案不是 1，而是 18。这说明 m 完全可能大于 n，不能枚举到 n 就停。
- n=17 时，答案必须是 7，这是样例。
- 输入遇到 0 要直接终止，不要再输出一行结果。
5. 枚举细节：m 的上限、预计算和更大数据
5.1 千万不要加“m <= n”的剪枝
很多第一次做的人会顺手写成for (m = 1; m <= n; ++m)，这是错的。n=14 时答案就是 18，远远超过 n。
原因很简单：约瑟夫环里每轮数 m 个，本质是“从当前位置向后偏移 m”，这个偏移可能绕过整个环好几圈。m 本身可以很大，取模之后的效果才会最终体现在位置上。你搜索的是原始 m，而不是每轮取模后的余数，所以不能按 n 限制搜索范围。
5.2 多组输入时可以考虑打表
UVA 的输入可能有很多个 n。最朴素写法是每个 n 独立搜索，但如果同一样例里同一个 n 出现多次，重复计算会显得浪费。更稳的做法是先读入所有 n，记录最大值，然后一次性算出来。
vector<int> query; int x; while (cin >> x && x) query.push_back(x); vector<int> ans(101, 0); for (int n = 13; n <= 100; ++n) { int m = 1; while (survivorIndex(n, m) != 11) ++m; ans[n] = m; } for (int n : query) cout << ans[n] << '\n';这样预处理一次，后续每组数据都是 O(1) 查表，本地测试也会舒服很多。
5.3 如果进一步追问，怎么处理更大的 n
如果 n 变成 1e7，枚举 m 加 O(n) 递推显然不行。标准约瑟夫有一种分段跳跃优化，核心思想是：当s + m < i时，下一轮不会触发取模，s会直接加上m。于是一次可以跳过很多轮，而不是每一轮都执行一次取模。
不过对 UVa 151 来说，n 很小，老老实实枚举就是最不容易出错的方案。除非你想拿这个题目练手写约瑟夫加速，否则不要为了炫技把代码写复杂。
6. 我实际踩过的三个坑
6.1 目标值写成 13，而不是 11
这是最典型的 off-by-one。递推式返回的是 0 基下标，而 13 号在“拿走 1 号后”的新序列里排第 12 个，下标是 11。
如果你非要用 1 基写法，也可以这样：
s = 1; for (int i = 2; i <= n - 1; ++i) { s = (s + m - 1) % i + 1; } if (s == 12) ...1 基序列里 13 号对应第 12 个元素，所以判断等于 12。两种写法本质一样，但千万不要混：递推用 0 基，判断却写成 13。
6.2 第一刀理解错，导致递推对象多了一个节点
某次我图省事，直接写了标准约瑟夫递推，然后把判断结果加 2。
// 错误示范 for (int i = 2; i <= n; ++i) s = (s + m) % i; if (s + 2 == 13) ...这样 n=17 会输出什么？m=7 的时候幸存下标是 1，加 2 后是 3，根本不是 13。问题就出在：标准约瑟夫会把 1 号当成正常参与者，而本题里 1 号是提前出局的。正确做法是在 n-1 个节点上做递推，并且从 i=1 开始。
6.3 用模拟链表写，逻辑没问题但容易 TLE
我也见过有人用 vector 模拟删除：
vector<int> v; // 把 2..n 放进去，然后循环 v.erase(...)n 小的时候能过，但代码又长又容易下标越界。递推写法只有一行核心代码，推导过程清楚了之后，写起来快得多。算法竞赛里，能推导就不该模拟，否则遇到多组数据会很被动。
最后分享一个扩展思路：如果题目改成“让 k 号区域最后幸存”，在“1 号先停掉”的规则下，只需要把判断条件改成TARGET = k - 2，其他代码完全不用动。因为这个题的本质就是：先移除 1 号，然后在一个长度为 n-1 的约瑟夫环里找幸存位置。理解了这一点，下次看到任何“先固定杀掉一个，再跑约瑟夫”的变形，你都能立刻知道从哪里下手。
