下午和朋友聊天的时候，有朋友提到了约瑟夫环问题。你和另外 n-1 个人围成一个圈，按 1，2，...，n 依次编号。第一个人从 1 开始报数，数到 k 的人会被杀掉，然后下一个人重新从 1 开始报数。如此往复，直到最后只剩下一个人。问题是，你应该如何选择自己的初始位置，才能保证最后不被杀掉呢？
速度越快的算法当然越好，毕竟这是一个生死攸关的问题。下面你将会看到，我们如何通过一些基本的数学推导最终得到这个问题的递推解。
初步思考
考虑这样一种相对简单的情况：总共有 5 个人，数到 3 的人被杀掉。那么，死亡过程如下图所示：
总共5人，数到3被杀
经过一番模拟之后，我们已经对约瑟夫环问题有了一个大概的直观理解。下面，尝试使用数学语言来描述这个问题。
哦对了，假如圆圈里只有你自己，那么你肯定就是最后的幸存者，这是一个极其有用的特殊情况。
建立模型
这些是我们的已知条件：
- 总共有 n 个人；
- 数到 k 的人将被杀死。
这个是我们的未知数：
- 位置 p，处在位置 p 上的人将会幸存下来。
推导求解
现在考虑一种泛化情形：总共有 n 个人，数到 k 的人被杀掉，其中 n >= k。幸存者的位置为 pn 。
显而易见，初始位置为 k 的人将会第一个被杀掉。此时，经过重新排序之后，问题变成了 n-1 个人的情形。幸存者的位置为 pn-1 。如果能够找到从 pn-1 到 pn 的递推关系，那么问题就解决了。
杀死第一个人之后，变成 n-1 个人的情况
重新排序之后，每个人的位置发生了下面这些变化：
- 1 -> n-k+1
- 2 -> n-k+2
- ...
- k-1 -> n-1
- k 被杀死
- k+1 -> 1
- ...
- pn -> pn-1
- ...
- n-1 -> n-k+1
- n -> n-k
很容易我们能得到这样一个关系式：pn = (pn-1 + k) % n 。再加上刚才讨论的特例，只有一个人的情况时，p1 = 1 。递推式就已经很明显了。
当然上文只讨论了 n>=k 的情形，实际上对于 n<k 的情形，刚才所得到的递推式依然适用，我们就不展开讨论了。
编码实现
既然递推式这么简洁明确，那么编码实现就不用写了吧？
