Joseph—约瑟夫环 线性复杂度

    说有n个要被处决的人（编号0~(n-1))，从0开始报数，报到(m-1)的会被杀掉，剩下的人继续从0开始报数，如此下去最后剩的一个人会存活下来。说Joseph发现了这个规律而且把他透露了出来，现在假如你在这n个人里面，你会选择几号位置站下。

　　很显然你会选择能活下来的那个位置，所以问题就是如何得到这个位置。

　　首先想到的是模拟(至少我笨脑子是这么想的)，但无论是用链表还是用数组这个时间复杂度都是比较高的，至少交题的时候会TLE，这里介绍一种线性时间的解法，出自大师Knuth的哦。

　　考虑下第一次杀人的时候，编号为k = (m - 1) % n的同学挂了，那我们从k + 1重新从0开始编号

　　k + 1 ==> 0

　　k + 2 ==> 1

　　……

　　……

　　k - 2 ==> n - 2

　　k - 1 ==> n - 1

　　好了，剩余的n - 1个同学又组成了一个新的Joseph环，对新环来说，编号k = (m - 1) % (n - 1)的同学会挂，如此下去，这里面似乎有某种规律可寻。

　　考虑到不会死的同学一直不会被杀(废话)，我们设i个同学时的不会挂的同学的编号(即解)为x，那么当死掉一个同学剩余i - 1个同学的时候，x仍然不会被杀，但此时的x已经由编号变换变成了x’，即x’是i - 1的情况时的解！一直推下去直到i - (i - 1)即1的情况，那1的时候解明显是0嘛！(注意编号是从0开始的)，倒推回来，那问题不就解决了么！

　　好了，分析清楚了剩下的就只是数学推导了，这个我比较烦，直接给公式吧：

　　向下变换：x’ = (x - (k + 1)) % i;

　　向上变换：x = (x' + k + 1) % i;

　　其中：　　k = (m - 1) % i;

　　带入可得：x = (x’ + m) % i;

令f[i]表示i个人玩游戏报m退出，最后胜利者的编号自然是f[n],递推公式：
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)