poj 2886 Who Gets the Most Candies?

题解：

约瑟夫还+反素数

约瑟夫还：线段树处理

发素数：dfs

这个题dfs时，不加上限会超过int

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn=500100;int prime[13]={1,2,3,5,7,11,13,17,19,23};struct TREE{    int l,r;    int sum;}tree[maxn*4];char s[maxn*2][20];int a[maxn*2];int n,m,bestx,bestnum;void dfs(int x,int k,int num,int limit){    if(x>n)return;    if(num>bestnum)    {        bestx=x;        bestnum=num;    }    else if(num==bestnum && x<bestx)    {        bestx=x;    }    int temp=1;    for(int i=1;i<=limit;i++)    {        temp*=prime[k];        if(x*temp>maxn)break;//不加这句话会搜爆，导致RE        dfs(x*temp,k+1,num*(i+1),i);    }}void build(int l,int r,int th){    tree[th].l=l;tree[th].r=r;tree[th].sum=0;    if(l==r)    {        tree[th].sum=1;        return;    }    int mid=(l+r)>>1;    build(l,mid,2*th);    build(mid+1,r,2*th+1);    tree[th].sum=tree[2*th].sum+tree[2*th+1].sum;}void add(int l,int r,int c,int th){    if(l==tree[th].l && r==tree[th].r)    {        tree[th].sum+=c;        return;    }    int mid=(tree[th].l+tree[th].r)>>1;    if(r<=mid)        add(l,r,c,2*th);    else if(l>mid)        add(l,r,c,2*th+1);    tree[th].sum=tree[2*th].sum+tree[2*th+1].sum;}int getnum(int l,int r,int th){    if(l>r)return 0;    if(tree[th].l==l && tree[th].r==r)        return tree[th].sum;    int mid=(tree[th].l+tree[th].r)>>1;    if(r<=mid)        return getnum(l,r,2*th);    else if(l>mid)        return getnum(l,r,2*th+1);    else        return getnum(l,mid,2*th)+getnum(mid+1,r,2*th+1);}int getlabel(int c,int th){    if(tree[th].l==tree[th].r)    {        return tree[th].l;    }    if(tree[2*th].sum>=c)        return getlabel(c,2*th);    else        return getlabel(c-tree[2*th].sum,2*th+1);}int main(){    while(scanf("%d%d",&n,&m)!=EOF)    {        for(int i=1;i<=n;i++)        scanf("%s%d",s[i],&a[i]);        bestx=1;bestnum=1;        dfs(1,1,1,20);        //xianduan        build(1,n,1);        int num=1,luck=m;        while(num<bestx)        {            //next            add(luck,luck,-1,1);            if(a[luck]>0)            {                a[luck]=a[luck]%(n-num);                if(a[luck]==0)a[luck]=n-num;                if(luck<n && getnum(luck+1,n,1)>=a[luck])                    luck=getlabel(getnum(1,luck,1)+a[luck],1);                else                    luck=getlabel(a[luck]-getnum(luck+1,n,1),1);            }            else            {                a[luck]=a[luck]%(n-num);                if(a[luck]==0)a[luck]=-(n-num);                if(luck>1 && getnum(1,luck-1,1)>=(-a[luck]))                    luck=getlabel(getnum(1,luck,1)+1+a[luck],1);                else                    luck=getlabel(getnum(1,n,1)-((-a[luck])-getnum(1,luck-1,1))+1,1);            }            num++;        }        printf("%s %d\n",s[luck],bestnum);    }    return 0;}