POJ2886Who Gets the Most Candies?(线段树之约瑟夫）

约瑟夫问题的升级版，每次出去的是前一个出去的人位置+手上的数字（正往前，负往后）。第i个出去的人拿的糖是i的约数的个数。求拿糖最多的人和他的糖果数。

这里用到了反素数的知识，在这直接打表

题目

AC代码：

#include<stdio.h>

#include<string.h>

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

const int N = ;

int v[N],sum[N<<],n,k;

char name[N][];

int rprim[]= {,,,,,,,,,,,,,,,,,,,,,,

,,,,,,,,,,,,,};///反素数

int nprim[]= {,,,,,,,,,,,,,,,,,,,,,,,,,,,

,,,,,,,,};///反素数的约数个数

void build(int l,int r,int rt)

{

    sum[rt]=r-l+;///sum储存这个区间有多少的数

    if(l<r)

    {

        int m=(l+r)>>;

        build(lson);

        build(rson);

    }

}

int update(int l,int r,int rt,int k)

{

    sum[rt]--;///这个区间减少一个数

    if(l==r)

        return l;///返回这个减少的数的原始下标

        int m=(l+r)>>;

    if(k<=sum[rt<<])///要找的第k个数小于等于左半区间的个数

        return update(lson,k);///就递归左子树

    else

        return update(rson,k-sum[rt<<]);///否则就在右子树，且k-左子树的个数

}

int main( )

{

    while(scanf("%d%d",&n,&k)!=EOF)

    {

        memset(name,,sizeof(name));

        for(int i= ; i<=n ;i++)

            scanf("%s%d",name[i],&v[i]);

        build(,n,);

        int tn=n,now,p=;

        while(rprim[p]<=n)///找出n里最大的反素数

            p++;

        for(int i= ; i<rprim[p-] ; i++)///反素数前的都出队

        {

            now=update(,n,,k);///当前出队的序号

            tn--;///剩下的人数

            if(v[now]>)///向前数

                k=(k-+v[now])%tn;///先减去本身这个位置 然后往前v个 再取模

            else

                k=((k+v[now])%tn+tn)%tn;///直接往后 然后要取模再取模保证正数

            if(k==)///如果刚好是tn 取模会变成0

                k=tn;

        }

        now=update(,n,,k);///得到第最大的反素数个出队的人的序号

        printf("%s %d\n",name[now],nprim[p-]);

    }

    return ;

}

不懂反素数的可以点击此链接：反素数