题目链接
在这里插入图片描述

约瑟夫环问题

假设有$n$个数，编号为$0,1,2,\cdots n-1$，其中0和$n-1$相连，形成一个环，如图：

1
2
3
4
5
6
graph LR
0((0))---1((1))
1((1)) --- 2((2))
2((2))---3((3))
3((3)) -- ....... ---n((n))
n---0

从0开始数$k$个，将这个数从环中移除，再数$k$个，再移除，问最后一个数是多少。
假设$n=7,k=3$。那么第一次删除2，数列变成:
0|1|2|3|4|5|6
-|-|-|-|-|-|-
0|1| |3|4|5|6
此时，1和3分离开了，为了使1和3连续，我们可以将列表重新编号，从被删除的下一个数开始编号，即：
\ |0|1|2|3|4|5|6
-|-|-|-|-|-|-|-
编号前|0|1| |3|4|==5==|6
编号后|4|5| |0|1|==2==|3
这样新表的下一个要删除的数编号为2，而旧表中为5。
不难发现，新旧表的下一个待删除的数的编号存在这样一个关系：

根据模数的性质，可以推出：

那么由6个数删到一个数的数列变化：
n | \ |0|1|2|3|4|5|6
-|-|-|-|-|-|-|-|-
7| -|0|1|2|$\color{red}{3}$|4|5|6
6| 编号前|0|1| |3|4|==5==|6
6| 编号后|4|5| |0|1|==2==|3
5|编号前|4|==5==| |0|1| |3|
5|编号后|1|==2==| |3|4| |0
4|编号前|1| | |3|4| |==0==
4|编号后|3| | |0|1| |==2==
3|编号前|3| | |0|==1==| | |
3|编号后|0| | |1|==2==| | |2
2|编号前|==0==| | |1|
2|编号后|==0==| | |1|
1|编号前| | | |==1==|
1|编号后| | | |==0==|
记$S_i$为$n=i$时的编号后的数列，$F(S_i)$为最后被删除的数在$S_i$中的编号，则：

并且有：$F(S_1)=0$
那么有：

求出了结果为3，与表格中的一致。

回归题目

而题目中是从m开始，而非从第一个开始。因为从第$k-1$个开始移除，那么接下来会从0开始编号，那么从$m-1$开始的话接下来会从$m-k$开始编号，并且题目从1开始编号，因此答案还要加上$m-k+1$。有因为 答案$+m-k+1$有可能小于等于0，因此再判断一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
int main() {
	int n, k, m;
	while (true) {
		cin >> n >> k >> m;
		if (!n && !k && !m) {
			break;
		}
		int ans = 0;
		for (int i = 2; i <= n; ++i) {
			ans = (ans + k) % i;
		}
		ans = (m - k + 1 + ans) % n;
		if (ans <= 0) {
			ans += n;
		}
		cout << ans << endl;
	}
}