题解 | #环形链表的约瑟夫问题(进阶)#

约瑟夫问题递推法

模拟的时间开销太大 不得不回头考虑递推关系：

• 将编号改为从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

#include<iostream>
#include<queue>
using namespace std;
 int getans(int n,int m){
     if(n==1)return 0;
     else{
         return (getans(n-1,m)+m)%n;
     }
 }

int main(){
    int m,n;
    while(scanf("%d%d",&n,&m)!=EOF){
        printf("%d\n",getans(n,m)+1);
    }
    return 0;
}