1 #include 
     
       2 #include 
      
        3 #define lson l, m, rt << 1 4 #define rson m+1, r, rt << 1 | 1 5  6 const int MAX_N = 500000 + 10; 7 int sum[MAX_N << 2]; 8 struct node 9 {10     char name[15];11     int val;12 }boy[MAX_N<<2];13 int ans[MAX_N];14 int id;15 int n, k;16 17 void build(int l, int r, int rt)18 {19     sum[rt] = r - l + 1;20     if (l == r)21         return ;22     int m = (l + r) >> 1;23     build (lson);24     build (rson);25 }26 27 int update(int p, int l, int r, int rt)28 {29     sum[rt]--;30     if (l == r)31     {32         return l;33     }34     int m = (l + r) >> 1;35     if (p <= sum[rt<<1])36     {37         return update (p, lson);38     }39     else40     {    41         return update (p - sum[rt<<1], rson);42     }43 }44 45 void Solve(){   //计算ans46     memset(ans,0,sizeof(ans));47     for(int i=1;i<=n;i++){48         ans[i]++;49         for(int j=2*i;j<=n;j+=i)50             ans[j]++;51     }52     int max=ans[1];53     id=1;54     for(int i=2;i<=n;i++)   //找出第几个人跳出获得的糖最多55         if(ans[i]>max){56             max=ans[i];57             id=i;58         }59 }60 61 int main(void)      //POJ 2886 Who Gets the Most Candies?62 {63     //freopen ("inF.txt", "r", stdin);64 65     while (~scanf ("%d%d", &n, &k))66     {67         build (1, n, 1);68         for (int i=1; i<=n; ++i)69         {70             scanf ("%s%d", &boy[i].name, &boy[i].val);71             //printf ("%s%d\n", boy[i].name, boy[i].val);72         }73         Solve();74         //int maxn = f(n);75         int mod = sum[1];76         boy[0].val = 0;77         int pos = 0;78         //printf ("%d\n", id);79         int m=id;80         while (m--)81         {82             if (boy[pos].val > 0)83                 k=((k-1+boy[pos].val-1)%mod+mod)%mod+1;84             else85                 k=((k-1+boy[pos].val)%mod+mod)%mod+1;86             pos = update (k, 1, n, 1);87             //printf ("%d ", pos);88             mod = sum[1];89         }90         printf ("%s %d\n", boy[pos].name, ans[id]);91     }92 }