约瑟夫环:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编号。
为取模方便,假设下标从0开始,倒推分析:
假设该轮有n个人,那么上一轮(n+1)人,编号为0的人上一轮编号为k,也即编号为f[n]的人上一轮编号为(f[n]+k)%(n+1)。
我们知道最后剩下的人在最后一轮编号肯定为0,那么这样不断倒推就可以推出其在第一轮的编号,也即他本来的编号。
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string> using namespace std; int f[1000005]; int main(){ //freopen("a.txt", "r", stdin); int n, m; while(~scanf("%d%d", &n, &m) && n && m){ f[1] = 0; for(int i = 2; i <=n; i++){ f[i] = (f[i-1]+m)%i; } cout << n << " " << m << " " << f[n]+1 << endl; } return 0; }