经典问题简述
有n个人，按编号1,2,3,…,n围成一圈，1与n相邻，现在从1开始往2的方向报数，报到m的人出列，然后下一个人从1开始重新报数，最后留下的人编号是几？
O(nm)暴力模拟
最朴素的想法，我们直接模拟报数的过程，暴力比较简单这里不多做解释。
O(n)解法
我们考虑能不能通过递推的方式求解，为了方便计算，我们先将所有人的编号用0~n-1表示，然后考虑每次有人出列后，将所有人的编号重排。
比如对于n=5,m=3，其原编号为
0 1 2 3 4
在2出列后，编号为
0 1 x 3 4
重排后为
2 3 x 0 1
我们观察一下出列后重排前后序列之间的关系
我们设出列时的人编号为k，重排前某人编号为p(p!=k)，重排后同一人编号为q，出列前总人数N
那么显然有q=(p-(k+1)+N)%N，且k=(m-1)%N，我们只需要看，0向后移动了k+1位，就可以很容易推出该结论
所以p=(q+k)%N=(q+m)%N，参照我们上面的定义，其实递推式已经很明显了
为了方便描述，设$f(i,m)$为i人按题目的游戏规则最后出列人的编号(0~i-1)，则有
于是我们的问题就能线性求解了
1 | for (int i = 2; i <= n; ++i) |
O(logn)解法
O(n)的解法似乎已经是最优解了，但人类不愿止步于此，于是又搞出来一个$O(\log n)$解法，当然，这里的$O(\log n)$是针对m比较小的情况，也就是认为m是一个常数，实际上m如果太大复杂度依然和$O(n)$或者$O(m)$差不多。
第一个解法
我们考虑改变递推的策略，考虑当一圈人报数回到0时是什么样子，当人数减小到$m$时对剩下的部分按$O(n)$递推方法求解，换句话说，我们加速上述算法中$n>m$的部分。
我们依然是0~n-1表示当前人的编号，报过一圈后从最后一个出列的人开始从0起重编。
例如n=8，m=3，那么初始序列为
0 1 2 3 4 5 6 7
报数后为
0 1 x 3 4 x 6 7
重排后为
2 3 x 4 5 x 0 1
现在我们依然是想通过$i-1$的答案推出$i$的答案，所以我们看看重排后的序列与重排前有什么关系
我们设$i-1$规模的答案为q，%i%规模的答案为p
首先我们观察到，最后一个x后人的个数为i%m，那么如果q < i % m，则$p=q+(i-i\bmod m)$，也就是将直到最后一个x的部分的人数加回来
否则，$p=q-i\bmod m+\lfloor\dfrac{q-i\bmod m}{m-1}\rfloor$，也就是说先减掉后面0~i%m-1的部分，然后加上前面删掉的人数，这里由于我们用的q是删后的序号，所以应该是除以$m-1$而不是除以$m$来得到删掉的人数。1
2
3
4
5
6
7
8int getans(int n, int m) {
if (n == 1)return 0;
if (n <= m)return (getans(n - 1, m) + m) % n;
int s = getans(n - n / m, m) - n % m;
if (s < 0)s += n;
else s += s / (m - 1);
return s;
}
第二个解法（有问题）
该解法可以求出第k(从0开始计数)个出列的人的编号，令k=n-1则得到原问题的答案。
显然我们可以知道，第k个出列的人是第$k\cdot m+m-1$次报数的人（这里以及以后所有的“第”后面都是从0开始计数的，便于计算）
那么我们通过这次报数往回追踪，每次计算上一次他是第几个报的数，就能找到最初当这个人报的数在$0~n-1$时报的数，即他的原始编号（从0计）。
此处我们利用的是总报数的次数与编号的关系，所以没有重排。
我们设报第p次的人为x，下一次他报数的次数为第q次，显然p可以表示为$p=a\cdot m+b,(0\le b< m)$
那么显然经过p次报数，出列了a个人，这时还剩n-a人，所以q=p+n-a，反过来就是p=q-n+a
现在的问题就是a是多少，我们需要建立a与q的关系，这样才能由q算出p，由上面的算式可以推出$q=p+n-a=a\cdot(m-1)+n+b$
由于x在报数后存活，所以b < m-1，因此$a=\lfloor\dfrac{q-n}{m-1}\rfloor$（这一步我觉得有问题）
最终算式就是$p=q-n+\dfrac{q-n}{m-1}$
所以我们的策略就很明显了
1 | int getans(int n, int m, int k) { |