题解 P2696 【慈善的约瑟夫】

· · 题解

这道题是一道很坑的递推题

分析：
设f[n]表示n个人最后出圈的人的编号，易知f[1]=1，f[2]=1，f[3]=3
设f[n]=x，f[n-1]=y，在n个人的情况下，第一次出圈的人是2号人，
把2号人挪到末尾，重新编号，如图：
原始编号：1 2 3 4 5 6 7 8 9 10
重新编号：9 - 1 2 3 4 5 6 7 8

则 x=(y+1)%n+1，即f[n]=(f[n-1]+1)%n+1

不要问我怎么推出来的我才不会告诉你我写了一下午

上代码

#include <iostream>
using namespace std;
const int N=100000;
int f[N+1];
int main()
{
    int n;
    cin>>n;
    f[0]=0;
    int money=n;
    for(int i=1;i<=n;i++)
    {
        f[i]=(f[i-1]+1)%i+1;
    }
    while(f[n]!=n) //只有f[n]==n才没有人退出
    {
        n=f[n];
    }
    cout<<money+n<<endl;
    return 0;
}