约瑟夫环

今天做题看到了顺便学习一下

问题描述：

有n个人围成一个环，然后给从某个人开始顺时针从1开始报数，每报到m时，将此人出环杀死，然后从下一个人继续从1报数，直到最后只剩下一个人，求这个唯一剩下的存活的人是谁？

 

分析：

1、模拟

复杂度O（n*m）

2、递推

复杂度O（n），好像也可以写递归，但感觉还是递推更简单

f[1]=0

f[i]=(f[i-1]+m)%i

具体证明可参考https://wenku.baidu.com/view/2a1e9b3383c4bb4cf7ecd1b4.html

这里摘出其中重要的部分：

3、最快的方法

复杂度O（m）

看上面那个递推式子，每次转移要%n，如果n很大的时候其实就是公差为m的等差数列

根据这个我们可以算出一段的，直接跳过

这是一道题：51nod1074

传送门

这里面比较难想的是跳过的时候要跳多少个k（这个里面是数k个人出环）

假设这个时候满足ans+k<i，设跳x个k

则有 i-(ans+x*k)<k

则 i-ans<(x+1)*k

最后是(i-ans)/k-1<x

我们可以用(i-ans+1)/k-1求得k

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
LL n,k,ans;

int main(){
	scanf("%lld%lld",&n,&k);
	for(LL i=1;i<=n;i++){
		if(ans+k<i){
			LL x=(i+1-ans)/(k-1)-1;
			if(x+i<n) i+=x, ans+=x*k;
			else ans+=(n-i)*k,i=n;
		}
		ans=(ans+k-1)%i+1;
	}
	printf("%lld\n",ans);
	return 0;
}