约瑟夫环

经典圆桌杀人问题。

经典约瑟夫环

问题很简单：有一个圆桌，圆桌上的每一个人依次有一个$0\sim n-1$的编号，从$0$号开始报数，每次把报到$k$的倍数的人给毙了，求最后被毙的是谁。

考虑倒推这个问题，当我们只剩下一个数时，它的编号一定是$0$。

因为它活到了最后一轮，所以上一轮的编号$pos=(k+0) \mod 2$，同理上上轮的编号为：$pos=((k+0)\mod 2 + k) \mod 3$，依次回推到原数列即可。

也有递推公式：$f_i=(f_{i-1}+k) \mod i$，$f_i$代表第$i$轮删除的数。