题目描述

约瑟夫问题来源于公元1世纪的犹太历史学家 Josephus 。

问题是这样的：有 $n$ 个人（分别以编号 $1，2，3...n$表示）围成一个圆圈，从编号为 $1$ 的人开始进行 $1～m$ 正向报数，报到 $m$ 的那个人出列；他的下一个人又从 $1$开始报数，数到 $m$ 的那个人又出列；如此重复下去，直到所有的人全部出列，求最后一个出列人的编号。

输入格式

输入文件仅有一行包含二个用空格隔开的整数 $n$，$m$。

数据范围

$2 \le n \le 100000$

$0 \lt M \le 1000$

输出格式

输出文件仅有一行包含一个整数表示一个整数，表示最后一个人在队列中的编号。

样例

8 3

7

完成程序

#include<bits/stdc++.h>
using namespace std;
int x[100001],L[100001],R[100001],n,m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		x[i] = i;
		R[i] = 填空(1); // 设置右指针
		L[i] = 填空(2); // 设置左指针
	}
	R[n] = 填空(3); // 尾巴的右指针指向头
	L[1] = 填空(4); // 头的左指针指向尾巴
	int HERE = 填空(5); // 第一次报号的位置
	while(填空(6)) // 当剩下 1 个人的时候退出循环
	{
		for(int i=1;i<m;i++) // 报数报 m 次 ，跳转 m-1 次
			HERE = 填空(7);
		
        // 删除 HERE 这个人
		R[填空(8)] = R[HERE];  // HERE 的左边的人的右指针指向 HERE 的右边
		填空(9) = L[HERE];  // HERE 的右边的人的左指针指向 HERE 的左边
		
		HERE = 填空(10); // 之前的 HERE 被删除了，下一轮从 HERE 右边的这个人开始报数
		
		n--; //人数减少 1 个
	}
	printf("%d",x[HERE]);	
	return 0;
}

填空(1)：{{ input(1) }}

填空(2)：{{ input(2) }}

填空(3)：{{ input(3) }}

填空(4)：{{ input(4) }}

填空(5)：{{ input(5) }}

填空(6)：{{ input(6) }}

填空(7)：{{ input(7) }}

填空(8)：{{ input(8) }}

填空(9)：{{ input(9) }}

填空(10)：{{ input(10) }}