POJ 2886 Who Gets the Most Candies?（反素数+数学推导+模拟+线段树||树状数组+二分）

落日映苍穹つ 2022-06-10 03:57 91阅读 0赞

*N* children are sitting in a circle to play a game.

The children are numbered from 1 to *N* in clockwise order. Each of them has a card with a non-zero integer on it in his/her hand. The game starts from the *K*\-th child, who tells all the others the integer on his card and jumps out of the circle. The integer on his card tells the next child to jump out. Let *A* denote the integer. If *A*is positive, the next child will be the *A*\-th child to the left. If *A* is negative, the next child will be the (−*A*)-th child to the right.

The game lasts until all children have jumped out of the circle. During the game, the *p*\-th child jumping out will get *F*(*p*) candies where *F*(*p*) is the number of positive integers that perfectly divide *p*. Who gets the most candies?

Input

There are several test cases in the input. Each test case starts with two integers *N*(0 < *N* ≤ 500,000) and *K* (1 ≤ *K* ≤ *N*) on the first line. The next *N* lines contains the names of the children (consisting of at most 10 letters) and the integers (non-zero with magnitudes within 108) on their cards in increasing order of the children’s numbers, a name and an integer separated by a single space in a line with no leading or trailing spaces.

Output

Output one line for each test case containing the name of the luckiest child and the number of candies he/she gets. If ties occur, always choose the child who jumps out of the circle first.

Sample Input

4 2
    Tom 2
    Jack 4
    Mary -1
    Sam 1

Sample Output

Sam 3

题解：

题意：

有n个人标号1,2...n围成圈，每个人有一张卡，有数字，开始从第k个人开始，他退出圈子，然后如果他的卡是正数x，那么从他开始向右数x个人为下一个出圈的人，如果是负数那么从他开始向左数x个人那个人出圈，求这一整个过程中，假设第i个人是第x次出圈，那么f（x）为x的因子个数，求f（x）最大值和该人的名字

线段树或者树状数组对于这题只是个工具。。重要的根据数学推导来模拟就很有难度了。。。。

对于这题求因子个数用筛法打个表就好了，线段树或者树状数组方面也很好写，但是对于数学推导+模拟我完全没啥思路。。。还是看了别人的博客理解了以后打了一遍，为什么线段树你要和数学联合起来欺负我这个弱渣。。。

我的代码里面因为看见数据范围是500000有点大不是很适合建树，有是单点更新，我就直接用树状数组了

我看的博客：[http://www.cnblogs.com/ZefengYao/p/6617350.html][http_www.cnblogs.com_ZefengYao_p_6617350.html]

ps：关于求因子不懂的我引用上面的博客的一段话解释

首先需要制定一份因子表factor\_num\[N\]，用于记录每一个数的因子的个数.做法类似于埃氏筛选。从小到大找素数，每找到一个素数，这个素数都有可能是比这个素数大的那些数的因子，每找到一个比当前素数大的并且能整除该素数的数，判断这个数中包含了多少当前素数因子。（108=3\*3\*3\*2\*2，所以它的素数因子为\{1，3，9，27\}\*\{1，2，4\}，一共有4\*3个因子）

我的代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    #define ll long long
    using namespace std;
    int sum[500005];//树状数组求第i个人之前还剩几个人
    int prime[500005];//求i的因子个数
    char name[500005][10];//名字
    int a[500005],n;//a存卡片
    int lowbit(int x)
    {
        return x&(-x);
    }
    int query(int x)//求第x个人前面有几个人还在
    {
        int s=0;
        while(x>0)
        {
            s+=sum[x];
            x-=lowbit(x);
        }
        return s;
    }
    void update(int x,int v)//x++是因为下标从0开始而树状数组要从1开始
    {
        x++;
        while(x<=n+1)
        {
            sum[x]+=v;
            x+=lowbit(x);
        }
    }
    int bin(int x)//二分查找有x个人的最左边位置。。对于这种东西写法依然很迷，我直接照打了，因为只要稍微改动一下就是wa
    {
        int l=0,r=n,mid;
        while(r-l>1)
        {
            mid=(l+r)/2;
            int t=query(mid);
            if(t<=x)
                l=mid;
            else
                r=mid;
        }
        return l;
    }
    void init()
    {
        int i,j;
        fill(prime,prime+500001,1);
        for(i=2;i<=500000;i++)//类似于素数筛法，打表处因子个数
        {
            if(prime[i]==1)
            {
                for(j=i;j<=500000;j+=i)
                {
                    int k=1,t=j;//k=1因为包括1
                    while(t%i==0)//求因子个数
                    {
                        t/=i;
                        k++;
                    }
                    prime[j]*=k;//乘上去
                }
            }
        }
    }
    int main()
    {
        int i,j,k,index,maxx;
        init();
        memset(sum,0,sizeof(sum));
        while(scanf("%d%d",&n,&k)!=EOF)
        {
            k--;//因为下标从0开始
            for(i=0;i<n;i++)
            {
                scanf("%s%d",name[i],&a[i]);
                update(i,1);
            }
            maxx=0;
            for(i=0;i<n;i++)//n次循环，每次走一人
            {
                if(prime[i+1]>maxx)//如果发现更大的，记录
                {
                    maxx=prime[i+1];
                    index=k;
                }
                update(k,-1);//去掉该人
                if(i<n-1)//这就是我不擅长的地方，数学推导加模拟
                {
                    int num=n-i-1;//当前剩余人数
                    int x=query(k)+a[k];//x为当前开始的位置
                    if(a[k]>0)//如果为卡片负数开始位置--
                        x--;
                    x=(x%num+num)%num;//听博客里说是处理负数的情况。。。我就是这里有点迷糊，x为下一个走的位置前面有多少人
                    k=bin(x);//二分查找符合条件的位置
                }
            }
            printf("%s %d\n",name[index],maxx);
        }
        return 0;
    }

[http_www.cnblogs.com_ZefengYao_p_6617350.html]: http://www.cnblogs.com/ZefengYao/p/6617350.html