约瑟夫问题

    约瑟夫问题是一类经典的又非常简单的基础数论问题

    题目大意(选班长)：

         N个人围成一个圈，依次编号为0..N-1。然后随机抽选一个数K，并0号候选人开始按从1到K的顺序依次报数，N-1号候选人报数之后，又再次从0开始。当有人报到K时，这个人被淘汰，从圈里出去。下一个人从1开始重新报数。最后一个人即是班长。

    换成示意图即是这样：

    设N=5，K=3

    1：从0开始报数，报到K，也就是2,2退出

    2：从3开始报数，遇到4返回0，0退出

    3：从1开始报数，报到4，4退出

    4：从1开始报数，报到3然后报回1,1退出，则3为班长

那么很容易想到朴素的递推算法：

f[1]=0;for(int i=2;i<=N;i++) f[i]=(f[i-1]+K)%i;cout<<f[N];

f[i]表示当有i个人时最后班长的编号。

    那么我们考虑多添加一个人对最后结果的影响

    最终肯定是多添加了一个元素导致整体K前移，而偏移的是K，所以要加回来。

我们可以发现，这种算法在普通时是可以使用的，但是如果N增大，时间、空间都会炸

                              (部分参照hihocoder)

我们假定一个初始序列：

0 1 2 3 4 5 6 7 8 9

当7号进行过报数之后：

0 1 2 - 4 5 6 - 8 9

在这里一轮报数当中，有两名候选人退出了，退出的候选人数量为N/K

由于此时起点为8，则等价于：

2 3 4 - 5 6 7 - 0 1

因此我们仍然可以从f[8]的结果来推导出f[10]的结果。

但需要注意的是，此时f[10]的结果并不一定直接等于(f[8] + 8) mod 10。

这是因为在序列(2 3 4 - 5 6 7 - 0 1)中，数字并不是连续的。

因此我们需要根据f[8]的值进行分类讨论。假设f[8]=s，则根据s和N mod K的大小关系有两种情况：

1) s < N mod K : s‘ = s - N mod K + N2) s ≥ N mod K : s‘ = s - N mod K + (s - N mod K) / (K - 1)

由于我们不断的在减小N的规模，最后一定会将N减少到小于K，此时N/K=0。

因此当N小于K时，就只能采用第一种递推的算法来计算了。

下面给出详细代码：(回家拿题乱写了一发，然后貌似就A了……)

#include<iostream>#include<cstring>#include<cstdio>using namespace std;inline int read(){    int x=0,f=1;char c=getchar();    for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1;    for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘;    return x*f;}int Josen(int N,int K){    int ret=0;    if(N==1) return 0;//如果N=1返回计算出的结果，避免无限递归    if(N<K){//迫不得已采用朴素算法求解        for(int i=2;i<=N;i++) ret=(ret+K)%i;        return ret;    }    else{        ret=Josen(N-N/K,K);//缩小问题规模        if(ret<N%K) ret=ret-N%K+N;//分类讨论        else ret=ret-N%K+(ret-N%K)/(K-1);        return ret;    }}int T;int N,K;int main(){    T=read();    while(T--){        N=read(),K=read();        cout<<Josen(N,K)<<endl;    }}

【数论】约瑟夫问题