参考资料：
[1]:http://www.hankcs.com/program/algorithm/poj-2886-who-gets-the-most-candies.html
题意：
抢糖：N个熊孩子围成一个圈，从第K个开始淘汰，每淘汰一个，出示手中的数字，决定下一个淘汰者，正数表示左手第n个，负数反之。每个人可以拿到的存活回数的因数个数的糖果，求拿到最多糖果数的孩子的名字以及糖果数。
（以上题意来自参考资料[1]）
下面谈谈我对参考资料[1]的理解：
下面介绍一下相对位置的概念（自己理解的，表达欠缺还请留言告知）：
假设初始有 6 个人，编号分别为 1~6
1 2 3 4 5 6（初始编号）
1 2 3 4 5 6（相对位置）
初始编号为2的小盆友离开后，相对位置变为：
1 3 4 5 6（初始编号）
1 2 3 4 5（相对位置）
那么，首先考虑这个问题，如何根据当前离开的小盆友的初始编号 k 和其手中的卡片 x 确定下一个小盆友离开的相对位置？
分两种情况：
假设当前还有 curTot 个小盆友，k 位置前有 before 个小盆友，k 位置后有 after 个小盆友（before + after = curTot）；
① x > 0
从 k 位置向右找第 x 个小盆友，相当于从第一个位置的小盆友向右找第 nex=(before+x)%curTot 个小盆友；
因为第一个小盆友的相对位置为 1，所以，需要查找的第 nex 个小盆友的相对位置为 nex+1；
② x < 0
从第 k 位置向左找第 x 个小盆友，相当于从第一个位置的小盆友向左找第 nex=(after+x)%curTot 个小盆友；
当前一共有 curTot 个小盆友，那，相当于从第一个位置的小盆友向右找第 nex= (curTot-nex)%curTot 个小盆友；
因为第一个小盆友的相对位置为 1，所以，需要查找的第 nex 个小盆友的相对位置为 nex+1；
相对位置求出来后，如何求解其对应的初始编号呢？？？
引用参考资料[1]博主的话就是 “这种区域修改可以活用BIT高效完成”；
怎么个活用法呢？
首先看一下BIT代码：
struct BIT
{
int bit[maxn];
void Init()
{
mem(bit,);
}
void Add(int t,int x)
{
while(t < maxn)
{
bit[t] += x;
t += lowbit(t);
}
}
int Sum(int t)
{
int sum=;
while(t > )
{
sum += bit[t];
t -= lowbit(t);
}
return sum;
}
}_bit;
初始，将 1~n 个小盆友全加入到BIT中；
for(int i=;i <= n;++i)
_bit.Add(i,);
那么，此时初始编号 i 对应的前缀和Sum(i)正好为 i 的相对位置：
i : 1 2 3 4 5 6
_bit.Sum(i) : 1 2 3 4 5 6
假设初始 i = 2 小盆友出队，调用_bit.Add(2,-1)
i : 1 2 3 4 5 6
_bit.Sum(i) : 1 1 2 3 3 4
如果我现在想知道相对位置为3的小盆友的初始编号，该怎么办呢？
你会发现，_bit.Sum(4) = 3，4正好是2好小盆友出队后相对位置为3的小盆友的编号；
那么，想要找相对位置为 pos 的初始编号，只需在_bit.Sum()中找第一个使 _bit.Sun(No) = pos 的No即可；
因为 _bit.Sum() 有序，所以，在查找的时候可以二分查找以提高效率；
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define lowbit(x) (x&-x)
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=5e5+; int n,k;
char name[maxn][];
int x[maxn];
int factor[maxn];
struct BIT
{
int bit[maxn];
void Init()
{
mem(bit,);
}
void Add(int t,int x)
{
while(t < maxn)
{
bit[t] += x;
t += lowbit(t);
}
}
int Sum(int t)
{
int sum=;
while(t > )
{
sum += bit[t];
t -= lowbit(t);
}
return sum;
}
int BS(int x)
{
int l=,r=n+;
while(r-l > )
{
int mid=l+((r-l)>>);
if(Sum(mid) >= x)
r=mid;
else
l=mid;
}
return r;//使Sum()=x 的第一个位置
}
}_bit;
void factorTable()
{
fill(factor,factor+maxn,);
for(int i=;i < maxn;++i)
{
if(factor[i] != )
continue;
for(int j=i;j <= maxn;j+=i)
{
int k=;
for(int m=j;m%i == ;m/=i,k++);
factor[j] *= k+;//j包含k个质数i
}
}
}
void Solve()
{
int candy=;
int index;
for(int i=;i <= n;++i)
{
if(candy < factor[i])
{
candy=factor[i];//更新candy
index=k;//第i个出队的编号是k（初始编号）
}
if(i == n)
break; _bit.Add(k,-);
int nex;
int curTot=n-i;//当前剩余小盆友的个数
if(x[k] > )//情况①
{
nex=(x[k]+_bit.Sum(k)-)%curTot;
nex++;
}
else//情况②
{
x[k]=-x[k];
nex=(x[k]+curTot-_bit.Sum(k))%curTot;//向左找第nex个
nex=(curTot-nex)%curTot;//转化为向右找
nex++;
}
k=_bit.BS(nex);//二分查找相对位置为nex的初始编号
}
printf("%s %d\n",name[index],candy);
}
int main()
{
factorTable();//预处理出因子表
while(~scanf("%d%d",&n,&k))
{
_bit.Init();
for(int i=;i <= n;++i)
{
scanf("%s%d",name[i],x+i);
_bit.Add(i,);
}
Solve();
}
return ;
}
其实，这道题被我搁置四天了，当时按照自己的思路写了个线段树的，wa了；
改了许久无果，无奈，搜了搜题解，第一个题解看的就是参考资料[1]，
不过，当时没怎么理解，又找了找其他人的博客，学到了一个新概念--反素数（可以提前打出反素数表，也可以提前打出因子表）；
这几天，训练赛几乎每天都有，忙着训练，忙着补题；
这道题只是在我闲暇时光看看，捋捋思路；
昨天晚上终于有点懵懂；
今天，又花费了一个多小时，终于AC了，不过，和[1]博主的代码不太一样，[1]博主的代码我还没怎么，理解透呢，只是有点懵懂；
或许，这就是大佬吧，写出的代码得让吾等蒟蒻看好久才能理解Orz