约瑟夫问题的一种亚线性做法

对于约瑟夫问题，假设一开始有 $n$ 个人，每个 $k$ 个人图图掉一个，我们两种常见的暴力做法是数组模拟和链表模拟，时间复杂度前者是 $O(n\log_k n)$ ，后者可以达到 $O(nk)$ 。

具体数学对 $k=2$ 的情况给出了一种构造，就是位移，将二进制数的第一位移到最后，形成的新二进制数就是最后剩下人的编号，时间复杂度 $O(\log_k n)$ ，对于 $k=3$ 的情况，根据尝试没有这种做法，于是另寻他路。考虑第一次图图掉第 $k$ 个人，相当于从 $k$ 位置开始处理 $n-1$ 人的情况，于是我们有以下递推公式：

f_n=(f_{n-1}+k) \% n

这样的时间复杂度是 $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;
int main()
#define int long long
{
	int n;
	scanf("%lld",&n);
	int ans=0;
	for (int i=1;i<n;i++){
        ans=(ans+3)%i;
	}
	printf("%lld\n",(ans+3)%n+1);
}

当然这样的做法可以优化，因为 $f_{n-1}$ 较小的情况，需要很多次 $+k$ 取模才能起作用，于是我们可以采用两种步长的做法，第一种跨度较大，用于提升速度，第二种跨度较小，为了处理取模。

#include <bits/stdc++.h>
using namespace std;
int main()
#define int long long
{
	int n;
	scanf("%lld",&n);
	int ans=0,cnt=0;
	for (int i=1;i<n;cnt++){
		if (i-1-ans>=3){
			int to=min(n-1,i-1+(i-1-ans)/3);
			int step=to-(i-1);
			ans=(ans+3*step)%to;
			i=to;
		}
		else {
			ans=(ans+3)%i;
		}
		i++;
	}
	printf("%lld\n",(ans+3)%n+1);
}

实测时间复杂度接近 $O(\log_k n)$ 。