用具体数学解决约瑟夫环问题

问题描述：

有 n 个人围成一个圈，每 q 个人踢掉一个人，问最后留下来的人是几号？

使用链表暴力求解时间复杂度是 O(qn)，递归的话是 O(n) ,使用这个方法可以加速到 O(logn).

解法思路：

假设初始编号为1，2，3 … n，现在考虑一种新的编号方式。

第一个人不会被踢掉，那么他的编号从n开始往后加1，变成n+1，然后第二个人编号变为n+2，直到第q个人，他被踢掉了。

然后第q+1个人编号继续加1，变成了n+q，依次下去。

考虑当前踢到的人编号为kq，那么此时已经踢掉了k个人，所以接下去的人新的编号为n+k(q-1)+1…。

所以编号为kq+d的人编号变成了n+k(q-1)+d，其中1<=d<q;

直到最后，可以发现活下来的人编号为qn，问题是怎么根据这个编号推出他原来的编号？

以 n=10 , q=3 为例，下图就是每个人新的编号：

令：
$$N=n+k(q-1)+d$$
则他上一次的编号为：
$$kq+d=kq+N-n-k(q-1)=k+N-n$$

$$又\because k=\frac{N-n-d}{q-1}=\lfloor \frac{N-n-1}{q-1}\rfloor$$

所以他上一次的编号可以写为：
$$\lfloor \frac{N-n-1}{q-1}\rfloor +N-n$$

因此最后存活的人可以这样计算：

N = qn
while N > n:
    N = k + N - n
ans = N

其中k等于：
$$k=\lfloor \frac{N-n-1}{q-1}\rfloor$$
如果用D=qn+1-N代替N,那么算法可以简化为：
$$\begin{array}{l}D=qn+1-N\\ =qn+1-\left(\lfloor \frac{(qn+1-D)-n-1}{q-1}\rfloor +qn+1-D-n\right)\\ =n+D-\left[\frac{(q-1)n-D}{q-1}\right]\\ =D-\lfloor \frac{D}{q1}\rfloor \\ =D+\lceil \frac{D}{q-1}\rceil \\ =\lceil \frac{q}{q-1}D\rceil \end{array}$$
算法伪代码：

D = 1
while D <= (q-1)n:
    D = k
ans = qn + 1 - D

其中k等于：
$$k=\lceil \frac{q}{q-1}D\rceil$$

代码展示：

//c++代码
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL Ceil(LL x, LL y) {
  return x / y + (x % y != 0);
}

LL J(LL n, LL q) {
  LL D = 1, end = (q - 1) * n;
  while (D <= end) {
​    D = Ceil(q * D, q - 1);
  }
  return q * n + 1 - D;
}

int main() {
  LL n, q;
  while (~scanf("%lld%lld", &n, &q)) {
​    printf("%lld\n", J(n, q));
  }
  return 0;
}