题意

给你 两个整数，要求求出约瑟夫问题中最后一个人是谁。

分析

总所周知，约瑟夫问题有模拟 ，线性 。这里解释一种 的解决方法。考虑到我们每次走 个删一个，那么在一圈以内我们可以删掉 个。我们可以模拟这个过程递归求解。由于每次递归问题规模变为 。通过归纳验证时间复杂度大概是

代码

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
int solve(int n,int k) {
    if(n==1)return 0;
    if(k==1)return n-1;
    if(k>n)return (solve(n-1,k)+k)%n;
    int res=solve(n-n/k,k);
    res -= n%k;
    if(res<0)res+=n;
    else res+=res/(k-1);
    return res;
}
int main() {
    while(1) {
        int n=read(),k=read();
        if(!n&&!k) return 0;
        printf("%d\n",solve(n,k)+1);
    }
}