约瑟夫问题

也许更好地阅读体验

$Description$Description

经典的约瑟夫问题
一开始有 $n$n 个人围成一个圈,他们的编号从 $0$0到 $n-1$n−1, 从 $1$1 开始顺时针报数, 报出 $m$m 的人被机关处决.
然后下一个人再从 $1$1 开始报数, 直到只剩下一个人.
问最后剩下的人的编号.

$n\le 10^{18},m\le 1000$n≤1018, m≤1000

$Solution$Solution

那些算法书总是把约瑟夫问题作为链表的例题来讲，初学者接触链表时还不会递推，于是一直以为只是一道链表题…

这么大的数据，当然不能链表模拟
考虑递推，还是那句话，递推的东西总是有联系的
递推时往往假设一个状态是已知的，然后试图推另一个状态，如果有递推式的话，我们就只要将最简单的状态手动求出即可
假设现在有 $n$n个人，第一个被处决的人的编号肯定是 $k=(m-1)\%n$k=(m−1)%n
当编号为 $k$k的人被处决后，接下来我们认为是从原编号为 $k+1$k+1的人开始重新编号，然后就是一个 $n-1$n−1个人的约瑟夫问题了
当然，这 $n-1$n−1个人的答案肯定不是最终答案，因为他是重新编号后的答案，所以我们要将其恢复原编号
因为新编号为 $0$0的人前面有 $m-1$m−1个人，也就是编号左移了 $m$m，所以最终的答案应该要加上 $m$m
设 $f\left[n\right]$f[n]为长度为 $n$n的最后剩下的人的编号
则有 $f\left[n\right]=\left(f\right[n-1]+m)\%n$f[n]=(f[n−1]+m)%n

于是我们得到了一个 $O\left(n\right)$O(n)的做法
但这还不够
我们继续看这个方程，发现 $n$n的答案可以被 $h$h共用
只需要满足 $f\left[n\right]+(h-n)m\&lt;n$f[n]+(h−n)m<n
也就是每次可以直接更新之后的 $k=\frac{n-f\left[n\right]}{m}$k=mn−f[n]​个长度的答案
于是就将复杂度大大降低了

$Code$Code

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年09月01日 星期日 15时54分02秒 *******************************/
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll n,m,ans,now;
int main()
{
	scanf("%lld%lld",&n,&m);
	ans=0,now=1;
	while (now<n){
		ll inc=min((now-ans)/m,n-now);
		if (!inc)	inc=1;
		now=now+inc;
		ans=(ans+inc*m)%now;
	}
	printf("%lld\n",ans+1);
	return 0;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧