嘟嘟噜 题解【约瑟夫环】【递归】

点击量：245

    约瑟夫环的加速处理。

目录

Description

由于众所周知的原因, 冈部一直欠真由理一串香蕉.

为了封上真由理的嘴, 冈部承诺只要真由理回答出这个问题, 就给她买一车的香蕉:

一开始有\(n\)个人围成一个圈, 从\(1\)开始顺时针报数, 报出\(m\)的人被机关处决. 然后下一个人再从\(1\)开始报数, 直到只剩下一个人.

红莉栖: “这不就是约瑟夫问题吗…”

伦太郎: “助手你给我闭嘴!”

真由理虽然已经晕头转向了, 但听到有一车的香蕉, 两眼便放出了光芒.

“那个呢, 真由氏很想要一车子的香蕉呢. 如果可以帮帮我的话, 我可以把一些香蕉分给你哟, 诶嘿嘿. 拜托你啦.”

Input Format

第一行一个整数\(T\) , 表示数据组数.

接下来\(T\)行, 每行两个整数 \(n, m\).

Output Format

对于每组数据, 输出一行一个整数, 表示幸存者的编号.

Sample

Input

5
4 6
2 8
2 9
8 8
7 9

Output

3 1 2 
4 7

Constraints

测试点编号	\(n\)	\(m\)
\(1\)	\(\le 10^5\)	\(\le 10^5\)
\(2\)	\(\le 10^6\)	\(\le 10^5\)
\(3\)	\(\le 10^9\)	\(\le 2\)
\(4\)
\(5\)		\(\le 3\)
\(6\)
\(7\)		\(\le 10^3\)
\(8\)		\(\le 10^4\)
\(9\)		\(\le 10^5\)
\(10\)

对于\(100\%\)的数据,\(1\le T\le 20,1\le n\le 10^9,1\le m\le 10^5\).

题解：

    题目就是要求\(n\le 10^9,m\le 10^5\)范围内的约瑟夫问题的解。因为之前没有做过这样的问题，只是从高一的OI招新考试（2333）中听说了这个东西，所以不知道有什么结论……

    花了二十分钟打了个表，找了很久的规律……

    本来以为横着会有循环节，这样稍微处理一下就是\(O(Tm)\)的了，但是多打了一些并没有……此时看了一下纵向貌似有一些规律，也看到了循环节，但是规律都不明显。然后我看到了形如第5列的”3,8,3,8“，貌似是\(d=5\)的等差？理智告诉我再去检查几个，发现都有这样的规律，但是也有很多不满足的。既然是纵向的，那么\(n\)，也就是人的总数会改变，那么上界就是会变的，考虑每次对\(n\)取膜……

    然后就把第5列拎出来了w：

    验证了这样的规律，这\(O(n)\)就实锤了。递推公式就是\(f_i\equiv f_{i-1}+m\bmod i\)，若\(f_i=0\)，则该轮最后留下来的编号是\(i\)。这就是著名约瑟夫问题的递推解法。但是让我把表给打出来了

    这个问题就是：大小为\(n\)的约瑟夫环出圈一个人，子问题就转化为了新的大小为\(n-1\)的约瑟夫环出圈后结果。递推开始位置与上一次出圈的位置有关。

    这里的递推主要影响因素就是取模，然后考虑\(m\)是固定的，因此当\(i\)很大时，加很多次\(m\)都不会涉及到\(i\)。那么我们可以加速，直接递推\(i\)到下一个取模的地方，甚至到后来\(i\)达到\(10^9\)数量级，\(m\)是\(10^5\)数量级，直接优化掉了\(10^4\)的时间。

    而这个加速幅度是与\(n,m\)有关的，而一开始增长较快，后来变得很慢，每变化一次，\(i\)都要改变\(\frac im\)的数量级，这个数字每次对\(i\)平方，总增长的次数大概就是\(\log n\)；而我这里为了保险起见没有推式子，就每次二分下一次变化边界在哪，当发现超过\(n\)时，在最后一段暴力求解即可。时间复杂度为\(O(m\log^2 n)\)。

    貌似取\(\frac im\)再稍微特判一下就不用多一个\(\log\)了啊…

    一般的约瑟夫问题直接列式子这样\(O(n)\)求解就可以了（吧

int solve(int n,int m)
{
    if(n==1)
        return 0;
    return (m+solve(n-1,m))%n;
}

Code：

#include<cstdio>
#include<cstring>
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        long long t=1,i=1;//i是当前的位置
        while(1)
        {
            long long l=1,r=n-i,mid;
            while(l<r)
            {
                mid=(l+r)>>1;
                if(t+mid*m>=(i+mid))
                    r=mid;
                else
                    l=mid+1;
            }
            if(i+l>n)
                break;
            i+=l;
            t=(t+l*m)%i;
            if(!t)
                t=i;
        }
        ++i;
        for(;i<=n;++i)
        {
            t=(t+m)%i;
            if(!t)
                t=i;
        }
        printf("%lld\n",t);
    }
    return 0;
}