关注公众号【算法码上来】，每日算法干货马上就来！
题目链接
题目描述
$0,1,\ldots,n-1$ 这 $n$ 个数字排成一个圆圈，从数字 $0$ 开始，每次从这个圆圈里删除第 $m$ 个数字。求出这个圆圈里剩下的最后一个数字。
例如，$0,1,2,3,4$ 这 $5$ 个数字组成一个圆圈，从数字 $0$ 开始每次删除第 $3$ 个数字，则删除的前 $4$ 个数字依次是 $2,0,4,1$，因此最后剩下的数字是 $3$。
示例1
输入：
n = 5, m = 3
输出：
3示例2
输入：
n = 10, m = 17
输出：
2说明：
- $1 \le n \le 10^5$
- $1 \le m \le 10^6$
题解
循环链表
用一个循环链表按顺序存储 $0$ 到 $n-1$ 中的数，然后每 $m$ 个数删除掉链表中的一个结点，最后剩下的数就是答案了。
这种方法时间复杂度是 $O(nm)$ ，显然太高了，所以这里也不会给大家实现代码。
递推法
首先 $n$ 个人的编号依次是 $0,1,\ldots,n-1$ ，然后踢掉了编号为 $k = (m-1)\%n$ 的人，这时候剩下的人编号为 $0,1,\ldots,k-1,k+1, \ldots,n-1$ 。
下一个踢掉的人就要从 $k+1$ 开始数了，所以我们把剩下的人编号从 $k+1$ 开始重新排个序，变成 $k+1, \ldots, n-1,0,\ldots,k-1$ 。这样编号又变成连续的了，而问题规模缩减成了 $n-1$ 个人。
剩下的这 $n-1$ 个人的编号我们做一下映射，映射成 $0,1,\ldots,n-2$ ，这样就能递推下去求解了。映射的公式就是，映射后的编号为 $x$ ，那么映射之前的编号就是 $(x+k+1)\%n = (x+m)\%n$ 。
也就是说，如果我们求出了 $n-1$ 个人最后剩下的人编号 $x$ ，那么 $n$ 个人最后剩下的人编号就是 $(x+m)\%n$ 。
用 $f(n)$ 表示 $n$ 个人最后剩下的人编号，那么就有：
$$
f(n) = (f(n-1) + m) \% n
$$
这样的话时间复杂度就降到了 $O(n)$ 。
对于本题这个方法已经够用了，但是如果 $n$ 非常大，比如 $n \le 10^{12}$ ，但是 $m$ 不是很大，比如 $m \le 1000$ ，那么这时候这种方法就会超时了。具体的题目请自行百度 HDU 3089 。
递推法加速
注意观察上面的递推式 $f(n) = (f(n-1) + m) \% n$ ，如果 $m$ 很小，而 $n$ 很大的话，递推到后面要加很多次 $m$ 才会对 $n$ 求余。所以我们可以直接一下子加很多次 $m$ ，然后再求余，这样就能加速了。
加了 $t$ 次 $m$ 之后，递推式变成了：
$$
f(n+t-1) = (f(n-1)+tm)\%(n+t-1)
$$
假设加了 $t$ 次 $m$ 之后才产生了取余，那么就有 $f(n-1) + tm \ge n+t-1$ ，即 $t \ge \frac{n-f(n-1)-1}{m-1}$ 。所以每次都可以加 $\left\lceil \frac{n-f(n-1)-1}{m-1} \right\rceil$ 个 $m$ ，代码实现时用下取整，也就是 $\left\lfloor \frac{n-f(n-1)+m-3}{m-1} \right\rfloor$ 。
此外还需要注意，如果发现 $i-1+t > n$ ，也就是后面都不需要取余了，那么就直接一步加到底，退出循环得到答案。
这个方法时间复杂度不是很好分析，但应该也是对数级别的。
数学法
这个方法在我之前的文章中已经讲过了：
韦阳的博客：具体数学-第8课（取整进阶）
知乎高赞回答也整理过了一遍：
世界上有哪些代码量很少，但很牛逼很经典的算法或项目案例？
大致思想也是重新编号，做编号映射，但是和上面递推法不同的是复杂度降到了对数级别。
这里就不详细讲了，大家可以去看上面的文章，这里直接给出伪代码：
D = 1
while D <= (m-1)n:
D = k
ans = mn+1-D其中 $k = \left\lceil \frac{m}{m-1}D \right\rceil$ 。
不过这个这里的编号是 $1$ 到 $n$ ，所以最后答案要减去 $1$ 。
这种方法将时间复杂度降到了 $O(\log_{\frac{m}{m-1}}{(m-1)n})$ ，用对数换底公式后得到 $O(\frac{\ln{(m-1)}+\ln{(n)}}{\ln{(m)}-\ln{(m-1)}})$ 。
可以看出，这种方法适用于 $n$ 特别大，但是 $m$ 特别小的情况。否则的话如果 $m$ 很大，分母会非常小，导致复杂度非常高。
代码
递推法（c++）
class Solution {
public:
int lastRemaining(int n, int m) {
int last = 0;
for (int i = 2; i <= n; ++i) {
(last += m) %= i;
}
return last;
}
};递推法加速（c++）
class Solution {
public:
int lastRemaining(int n, int m) {
if (m == 1) return n-1;
int last = 0, t = 1;
for (int i = 2; i <= n; i+=t) {
t = (i-last+m-3) / (m-1);
if (i+t-1 > n) {
last += (n-i+1)*m;
break;
}
(last += t*m) %= (i+t-1);
}
return last;
}
};数学法（c++）
class Solution {
public:
int lastRemaining(int n, int m) {
long D = 1, end = (long)n*(m-1);
while (D <= end) {
D = (m*D+m-2) / (m-1);
}
return (long)n*m-D;
}
};
