And Then There Was One

题目链接

约瑟夫环问题

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

从0开始数$k$k个，将这个数从环中移除，再数$k$k个，再移除，问最后一个数是多少。
假设$n=7,k=3$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。
不难发现，新旧表的下一个待删除的数的编号存在这样一个关系：
$DeletedNode_{新表}=（DeletedNode_{旧表}-k）\bmod 旧表中剩余的数的个数$DeletedNode新表​=（DeletedNode旧表​−k）mod旧表中剩余的数的个数
根据模数的性质，可以推出：
$DeletedNode_{旧表}=（DeletedNode_{新表}+k）\bmod 旧表中剩余的数的个数$DeletedNode旧表​=（DeletedNode新表​+k）mod旧表中剩余的数的个数
那么由6个数删到一个数的数列变化：

n	\	0	1	2	3	4	5	6
7	-	0	1	2	$\color{red}{3}$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	编号前	0			1
2	编号后	0			1
1	编号前				1
1	编号后				0

记$S_i$Si​为$n=i$n=i时的编号后的数列，$F(S_i)$F(Si​)为最后被删除的数在$S_i$Si​中的编号，则：
$F(S_i)=(F(S_{i-1})+k)\bmod |S_i|$F(Si​)=(F(Si−1​)+k)mod∣Si​∣
并且有：$F(S_1)=0$F(S1​)=0
那么有：
$F(S_2)=(F(S_1)+3)\bmod 2=1\\ F(S_3)=(F(S_2)+3)\bmod 3=1\\ F(S_4)=(F(S_3)+3)\bmod 4=0\\ F(S_5)=(F(S_4)+3)\bmod 5=3\\ F(S_6)=(F(S_5)+3)\bmod 6=0\\ F(S_7)=(F(S_6)+3)\bmod 7=3\\$F(S2​)=(F(S1​)+3)mod2=1F(S3​)=(F(S2​)+3)mod3=1F(S4​)=(F(S3​)+3)mod4=0F(S5​)=(F(S4​)+3)mod5=3F(S6​)=(F(S5​)+3)mod6=0F(S7​)=(F(S6​)+3)mod7=3
求出了结果为3，与表格中的一致。

回归题目

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

#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;
	}
}