【题解】LA 3882【And Then There Was One】

分析

这题是约瑟夫问题的变种,就是从第$m$开始而不是原版的从第$1$个数,直接上递推就好了,编号为$0$~$n-1$的$n$个数排成一行,从$0$开始没$k$个数删一个,最后留下的数记为$f(n)$,则$f(n)=(f(n-1)+k)\mod n$,原因就是删除一个数之后,可以把所有数重新编号。如图26:

本题第一个删除的数为$m$,因此答案为$(m-k+1+f[n])\mod n$

代码

#include<cstdio>
const int MAXN = 10000 + 2;
int f[MAXN];

int main(){
  int n,k,m;
  while(scanf("%d %d %d",&n,&k,&m) == 3 && n){
    f[1] = 0;
    for(int i = 2;i <= n;i++)f[i] = (f[i - 1] + k) % i;
    int ans = (m - k + 1 + f[n]) % n;
    if(ans <= 0) ans += n;
    printf("%d\n",ans);
  }

  return 0;
}