约瑟夫问题的一些解法

约瑟夫问题：

有n个人，编号为\(1..n\)，从第1个人开始报数，报到m的人离开，求最后的幸存者。

算法1（Simple算法）：

用队列模拟，可以算出每一次出队的人。

时间复杂度\(O(nm)\)

当n很小而m很大时，可以通过取膜将\(O(nm)\)优化为\(O(n^2)\)

注：

编号整体\(+x\)的意思就是1号变为\(x+1\)号，2号变为\(x+2\)号......，\(n-x\)号变为\(n\)号，\(n-x+1\)号变为1号，......\(n\)号变为\(x\)号。

编号整体\(-x\)的意思就是1号变为\(n-x+1\)号，\(2\)号变为\(n-x+2\)号......，\(x\)号变为\(n\)号，\(x+1\)号变为1号，......\(n\)号变为\(n-x\)号。

算法2：

设\(f(n)\)表示n个人报数最后的幸存者。 首先第一次第m个人离开，剩下的\(n-1\)人编号整体-m，然后就变成了一个n-1个人的问题。 算完以后整体右移回去这m位，如果\(>n\)就\(-n\)

所以发现递推式：\(f(n)=(f(n-1)+m-1)\mod n + 1\) ### 算法3(\(m=2\))： 当\(m=2\)时，首先会将所有偶数编号的人移出去。

然后如果\(n\)是个偶数，则下一次会移出3，等等，也就是说可以直接化为n/2人的问题，其中原来的\(2x-1\)号变为了\(x\)号。计算出来的答案要\(\times 2-1\)

如果是个奇数，下一次会让1号出去，我们就可以直接把1号移出去然后把其它的奇数编号重编号\(2x-3\)变为\(x\)，就化为了\(\lfloor\frac{x}{2}\rfloor\)的问题。 算出的答案要\(\times 2 - 3\)

所以发现了递推公式：

\[ f(n)=\begin{cases}f(\frac{n}{2})\times2-1 & n \equiv 0(\mod 2) \\ f(\lfloor\frac{n}{2}\rfloor)\times 2 - 3 & n \equiv 0(\mod 2)\end{cases} \]

时间复杂度\(O(log_2n)\) ### 算法4： 对于算法2，我们发现有很多时候取膜并没有用。 那么我们可以合并很多个取膜。 然后就快了很多。 能过\(n\le 10^9\),\(m\le 10^5\)

算法3,4的代码：

/*
Author: CNYALI_LK
LANG: C++
PROG: mayuri.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define all(x) x.begin(),x.end()
#define end(...) {printf(__VA_ARGS);exit(0);}
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs

int yues(int x){//m=2
    if(x==1)return 1;
    else if(x&1)return 2*yues(x>>1)+1;
    else return 2*yues(x>>1)-1;
}
int main(){
    freopen("mayuri.in","r",stdin);
    freopen("mayuri.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T){
    int n,m;
    scanf("%d%d",&n,&m);
        int s=1,t=1,k;
        while(t<=n){
            k=(t-s)/(m-1);
            if(t+k>=n){
                s=s+m*(n-t);
                printf("%d\n",s);
                break;
            }
            s+=m*k;//压缩多个(+ m-1) mod n + 1 
            t+=k;
            ++t;
            s=(s+m-1)%t+1;
        }
        --T;
    }
    return 0;
}