poj 2886

线段树+反素数

线段树区间存储未出局的小朋友数（与poj2828类似）

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 500100;
char name[maxn][11];
int val[maxn];
/* a为反素数表，b为对应的约数个数 */
int a[37]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,
           55440,83160,110880,166320,221760,277200,332640,498960,500001};
int b[37]={1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144,160,168,180,192,200,1314521};

struct Node
{
    int l, r, sum;
}st[maxn<<2];

void build(int l, int r, int rt)
{
    st[rt].l = l;
    st[rt].r = r;
    st[rt].sum = r - l + 1;
    if (l == r) return ;
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
}

/* 求当前留下的孩子中第num个空位置 */
int query(int num, int rt)
{
    st[rt].sum--;
    if (st[rt].l == st[rt].r)
        return st[rt].l;
    if (num <= st[rt<<1].sum)
        return query(num, rt << 1);
    return query(num - st[rt<<1].sum, (rt << 1)+1);
}

int main(){
    int n, k;
    while (scanf("%d %d", &n, &k) != EOF){
        int i = 0, Max = 0, p = 0; /* 第p个出去的孩子得到最多的糖果，为Max */
        while (a[i] <= n)
            i++;
        p = a[i-1];
        Max = b[i-1];
        build(1, n, 1);
        for (i = 1; i <= n; ++i)
            scanf("%s %d", &name[i], &val[i]);
        k--;
        int idx; /* idx为当前出去的孩子的原始位置 */
        for (i = 0; i < p; ++i){/* 只要求出第p个出去的孩子即可 */
            n--;
            idx = query(k+1, 1);
            if(i==p-1)break;
            if (val[idx] > 0)
                k = (k+val[idx]-1)%n;
            else
                k = ((k+val[idx])%n+n)%n;
        }
        printf("%s %d\n", name[idx], Max);
    }
    return 0;
}