HDU2925 Musical Chairs（约瑟夫环）

题目链接

约瑟夫环：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;
}