Description
N children are sitting in a circle to play a game.
The children are numbered from 1 to N in clockwise order. Each of them has a card with a non-zero integer on it in his/her hand. The game starts from the K-th child, who tells all the others the integer on his card and jumps out of the
circle. The integer on his card tells the next child to jump out. Let A denote the integer. If A is positive, the next child will be the A-th child to the left. If A is negative, the next child will be the (−A)-th
child to the right.
The game lasts until all children have jumped out of the circle. During the game, the p-th child jumping out will get F(p) candies where F(p) is the number of positive integers that perfectly divide p.
Who gets the most candies?
Input
(consisting of at most 10 letters) and the integers (non-zero with magnitudes within 108) on their cards in increasing order of the children’s numbers, a name and an integer separated by a single space in a line with no leading or trailing
spaces.
Output
Output one line for each test case containing the name of the luckiest child and the number of candies he/she gets. If ties occur, always choose the child who jumps out of the circle first.
Sample Input
4 2 Tom 2 Jack 4 Mary -1 Sam 1
Sample Output
Sam 3
题目意思是：第一行输入两个数n,k，分别代表n个人和一开始最先跳出的位置k，接下来输入n个人的名和手里的的数字cd，这n个人从上到下以顺时针形成一个圆环，首先第k个人先出环，再当cd为正数时顺时针走cd步，那么数到的这个人就跳出环，以此类推，当cd为负数时，逆时针走（-cd）步，第m个跳出的人得m的不重复因子的个数（v）个糖果。求出得到得到最多的糖果的人，如果有多个一样的求最先跳出的，输出名子和得到糖果的数量。
#include<stdio.h>
#include<string.h>
#define N 500000
struct pepoler
{
char nam[12];
int cd;
}pep[N+5];
int tree[4*N],candy[N+5];
void HASHI_candy()//打表计算因子的个数（糖果）
{
memset(candy,0,sizeof(candy));
for(int i=1;i<N;i++)
{
candy[i]++;
for(int j=i+i;j<=N;j+=i)
candy[j]++;
}
}
void builde_1(int l,int r,int k)
{
int m=(l+r)/2;
tree[k]=r-l+1;//代表在当前范围内的人数
if(l==r) return ;
builde_1(l,m,k*2); builde_1(m+1,r,k*2+1);
}
int lalive,MJ,id,jmpid;
void updata_1(int l,int r,int k,int jmp,int J)
{
int m=(l+r)/2;
tree[k]--;//跳出一个人则减1
if(l==r)
{
if(J==MJ) id=l;//标记得到糖果最多位置
jmpid=l;//记录跳出环的人的位置
return ;
}
if(tree[k*2]>=jmp)
updata_1(l,m,k*2,jmp,J);
else{
lalive+=tree[k*2];//记录跳出的这个人前方还有多少个人还活着
updata_1(m+1,r,k*2+1,jmp-tree[k*2],J);
}
}
int main()
{
int n,k,ralive,jmp,cd;
HASHI_candy();
while(scanf("%d%d",&n,&k)>0)
{
getchar(); MJ=1;
for(int i=1;i<=n;i++)
{
scanf("%s%d",pep[i].nam,&pep[i].cd);
if(candy[MJ]<candy[i]) MJ=i;
}
builde_1(1,n,1);
jmp=k;
for(int J=1;J<=MJ;J++)
{
lalive=0;
updata_1(1,n,1,jmp,J);
ralive=n-J-lalive;
if(J==MJ) continue;
if(n-J==1) { jmp=1;continue;}
cd=pep[jmpid].cd;
if(cd<0){
cd=-(cd%(n-J)); if(!cd) cd=n-J;
if(cd<=lalive) cd=lalive-cd+1;
else cd=ralive-(cd-lalive)+1+lalive;
}
else {
cd=cd%(n-J); if(!cd) cd=n-J;
if(cd<=ralive) cd=lalive+cd;
else cd=cd-ralive;
}
jmp=cd;
}
printf("%s %d\n",pep[id].nam,candy[MJ]);
}
}