自动搬运

查看原文

来自洛谷，原作者为

	asdfo123 An unexperienced Acmer

搬运于2025-08-24 21:30:45，当前版本为作者最后更新于2020-10-19 08:08:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

约瑟夫问题典型例题

这类问题模板：

n 个人标号 1~ n。逆时针站一圈，从1号开始，每一次从当前的人逆时针数m个，然后让这个人出局。问最后剩下的人是谁。

我们思考，有 $N$ 个猴子，如果现在一个猴子出列，那么剩下的猴子就变成了 $(n-1)$ 个猴子数数的子问题。

我们设 $f_i$ 为 $i$ 个猴子数数选出的大王编号，那么由于新的子问题要从下一个猴子开始数，编号要加上 $m$

那么可以得到递推式子： $f[1] = 0$

$f[i] = (f[i-1]+m)\ mod \ i\ (i>1)$

这样是编号从0开始的，我们想要编号从１开始

那么： $f[0] = 0$

$f[i] = (f[i-1]+m-1)\ mod \ i+1\ (i>=1)$

最后别忘了要从 $a$开始统计最大值...

代码：

#include <bits/stdc++.h>
using namespace std;
int f[1000010];
int vis[1000010];
int a,b,m;
int main()
{
	scanf("%d%d%d",&a,&b,&m);
	f[1] = 1;
	int ans = 0;
	for(int i = 1;i <= b;i++)
	{
		f[i] = (f[i-1]+m-1)%i+1;
		if(i>=a)
		{
			vis[f[i]]++;
			ans = max(ans,vis[f[i]]);
		}
	}
	printf("%d\n",ans);
	for(int i = 1;i <= b;i++)
	{
		if(vis[i] == ans) printf("%d ",i);
	}
	return 0;
}