3
HDU2925 Musical Chairs（约瑟夫环）
source link: https://arminli.com/hdu2925/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
HDU2925 Musical Chairs（约瑟夫环）
March 13, 2016
约瑟夫环：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;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK