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

问题描述：

有 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 为例，下图就是每个人新的编号：

1	2	3	4	5	6	7	8	9	10
11	12	T	13	14	T	15	16	T	17
18	T		19	20		T	21		22
T			23	24			T		25
			26	T					27
			28						T
			29
			30

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

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

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

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

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

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

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

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

---

代码展示：

//c++代码
#include 
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;
}