题目链接：

【题目】N个孩子顺时针坐成一个圆圈，从1~N编号，每个孩子手中有一张标有非零整数的卡片。第K个孩子先出圈，如果他手中卡片上的数字A>0，下一个出圈的是他左手边第A个孩子。A<0，下一个出圈的是他右手边第(-A)个孩子。第p个出圈的孩子会得到F(p)个糖果，F(p)为p的因子数。输出得到糖果数最多的孩子的名字及糖果数目。

【思路】孩子数目很大（1~500000），于是想到要用线段树来优化，然后就是模拟出圈过程。并更新最大糖果数目。然后因为是一个圈，编号就每次都要取模，因为取模结果总是0~num-1，而编号确实1~num，所以取模要编号K-1，求出结果后再K+1。

①A>0, 因为这个人出去了，那么后面的人的编号都会先减一所以这里的要K-2。于是下一个出圈的就应该是剩余孩子中的第((K-2+A)%num+num)%num+1个。

②A<0，因为这个人出去，对前面的人是没有影响的。于是下一个出圈的就应该是剩余孩子中的第((K-1+A)%num+num)%num+1个。

这里的F(p)我是直接数组暴力打表得来的，最后1500MS过了，看网上有一种反素数，更加快，有空去学。

 

【涨姿势】代码中注释的地方在问了学长之后搞明白了，有负数的时候必须模两次，比如-14%6，(-14+6)%6和((-14)%6+6)%6的结果是不一样的，也就是说n%k，当n大于k的负两倍时，第一次模能够让它保证值落在-1倍~1倍之间，第二次模让它变成正数。

下面贴代码：

1 /*  2 ** POJ 2886 Who Gets the Most Candies  3 ** Created by Rayn @@ 2014/05/09  4 ** 线段树  5 */  6 #include 
      
         7 #include 
       
          8 #include 
        
           9 #include 
         
           10 using namespace std; 11 const int MAX = 500100; 12  13 struct Child { 14     char name[12]; 15     int A; 16 } child[MAX]; 17  18 int n, k, tree[MAX<<2], candy[MAX]; 19  20 void GetCandy() //计算约数 21 { 22     memset(candy, 0, sizeof(candy)); 23     int limit = (int)sqrt(MAX); 24     for(int i=1; i
          
           > 1; 46     BuildTree(rt<<1, l, mid); 47     BuildTree(rt<<1|1, mid+1, r); 48 } 49 int Update(int rt, int l, int r, int val) 50 { 51     tree[rt]--; 52     if(l == r) 53     { 54         return l; 55     } 56     int ans, mid = (l + r) >> 1; 57     if(val <= tree[rt<<1]) 58         ans = Update(rt<<1, l, mid, val); 59     else 60         ans = Update(rt<<1|1, mid+1, r, val-tree[rt<<1]); 61     tree[rt] = tree[rt<<1] + tree[rt<<1|1]; 62     return ans; 63 } 64 int main() 65 { 66 #ifdef _Rayn 67     //freopen("in.txt", "r", stdin); 68 #endif 69  70     GetCandy(); 71     while(scanf("%d%d", &n, &k) != EOF) 72     { 73         memset(tree, 0, sizeof(tree)); 74         BuildTree(1, 1, n); 75         for(int i=1; i<=n; ++i) 76         { 77             scanf("%s%d", child[i].name, &child[i].A); 78         } 79         int maxVal = -1, maxPos, pos; 80         int num = n; 81         for(int i=1; i<=n; ++i) 82         { 83             pos = Update(1, 1, n, k); 84             num--; 85             if(candy[i] > maxVal) 86             { 87                 maxVal = candy[i]; 88                 maxPos = pos; 89             } 90  91             if(num == 0) 92                 break; 93             /* 94             ** 因为取模结果总是0~num-1,所以取模要编号k-1，求出结果后再+1。 95             ** A>0, 因为这个人出去了，那么后面的人的编号都会先减一 96             ** 所以这里的k要再-1。 97             ** A<0，因为这个人出去，对前面的人是没有影响的。 98             */ 99             if(child[pos].A > 0)100             {101                 k = ((k-2 + child[pos].A) % num + num) % num + 1;102             }103             else104             {105                 //为何模两次就对了呢106                 //k = ((k-1 + child[pos].A + num) % num + 1;107                 k = ((k-1 + child[pos].A) % num + num) % num + 1;108             }109         }110         printf("%s %d\n", child[maxPos].name, maxVal);111     }112     return 0;113 }