约瑟夫问题递推法
模拟的时间开销太大 不得不回头考虑递推关系：
- 将编号改为从0开始,记f(n,m)为原问题的解
- 由于第一次遍历了0~(m-1)%n，则第二次遍历相当于将整个队伍循环左移了k位(k=m%n)
- 所以子问题f(n-1,m)的解循环右移k位即为原问题的解f(n,m)
- f(n,m)=(f(n-1,m)+m)%n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include<cstdio>
using namespace std;
int getLive(int i,int m){
if(i==1) return 0;
return (getLive(i-1,m)+m)%i;
}
int main() {
int n,m;
scanf("%d %d",&n,&m);
printf("%d\n",getLive(n,m)+1);
return 0;
}
// 64 位输出请用 printf("%lld")
