poj 2886 Who Gets the Most Candies?（线段树和反素数）

题目：http://poj.org/problem?id=2886

题意：N个孩子顺时针坐成一个圆圈且从1到N编号，每个孩子手中有一张标有非零整数的卡片。

第K个孩子先出圈，如果他手中卡片上的数字A大于零，下一个出圈的是他左手边第A个孩子。

否则，下一个出圈的是他右手边第(-A)个孩子。第p个出圈的孩子会得到F(p)个糖果，F(p)为p的因子数。求得到糖果数最多的是哪个孩子及得到多少糖果。

跟上一个 约瑟夫环的题目很像，就是加了一个反素数。

虽然我还是不太理解，但还是无耻的从别人的结题报告上把反素数表copy了下来。。。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int val[maxn];

 char name[maxn][];

 int a[]= {,,,,,,,,,,,,,,,,,,,

             ,,,,,,,,

             ,,,,,,,,

            };    //反素数表

 int b[]= {,,,,,,,,,,,,,,,,,,,,,,,,,

             ,,,,,,,,,,

            };   //反素数对应的值

 struct node

 {

     int l, r, sum;

 }tr[maxn<<];

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

 {

     tr[t].l = l;  tr[t].r = r;

     tr[t].sum = r - l + ;

     if(l == r)

         return;

     int mid = (l+r)>>;

     build(*t, l, mid);

     build(*t+, mid+, r);

 }

 int query(int num, int t)

 {

     tr[t].sum--;

     if(tr[t].l == tr[t].r)

     return tr[t].l;

     if(tr[*t].sum >= num)

     return query(num, *t);

     else

     return query(num-tr[*t].sum, *t+);

 }

 int main()

 {

     int n, k, i, p, Max;

     int x;

     while(~scanf("%d%d", &n, &k))

     {

         i = ;

         Max = ; p = ;

         while(a[i] <= n)

         i++;

         p = a[i-]; Max = b[i-];  //第几个出去的。最大值

         build(, , n);

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

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

         for(i = ; i < p; i++)

         {

             n--;

             x = query(k, );

             if(n == )  break;

             if(val[x] > )

             k = (k-+val[x]-)%n + ;

             else

             k = (k-+val[x]%n+n)%n + ;

         }

         printf("%s %d\n",name[x], Max);

     }

     return ;

 }