有 n 个人围成一个圈,每 q 个人踢掉一个人,问最后留下来的人是几号?
解法思路:
第一个人不会被踢掉,那么他的编号从 n 开始往后加 1 ,变成 n+1 ,然后第二个人编号变为 n+2 ,直到第 q 个人,他被踢掉了.
考虑当前踢到的人编号为 kq,那么此时已经踢掉了 k 个人,所以接下去的人新的编号为 n+k(q-1)+1....
所以编号为 kq+d 的人编号变成了 n+k(q-1)+d ,其中 1<=d<q;
直到最后,可以发现活下来的人编号为 qn ,问题是怎么根据这个编号推出他原来的编号?
以 n=10  q=3 为例,下图就是每个人新的编号:
\quad N=n+k(q-1)+d
\quad kq+d=kq+N-n-k(q-1)=k+N-n
所以他上一次的编号可以写为:
如果用 D=qn+1-N 代替 N 那么算法可以简化为: