Who Gets the Most Candies?

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

There are several test cases in the input. Each test case starts with two integers  N (0 <  N  ≤ 500,000) and K (1 ≤ K ≤ N) on the first line. The next N lines contains the names of the children (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个孩子顺时针坐成一个圆圈且从1到N编号，每个孩子手中有一张标有非零整数的卡片。第K个孩子先出圈，如果他手中卡片上的数字A大于零，下一个出圈的是他左手边第A个孩子。否则，下一个出圈的是他右手边第(-A)个孩子。第p个出圈的孩子会得到F(p)个糖果，F(p)为p的因子数。求得到糖果数最多的是哪个孩子及得到多少糖果。

  
 
  
其实出圈这个操作就是约瑟夫环……线段树求约瑟夫环的方法每次算出出圈的是第几个数，然后维护区间还有多少空位,然后将出圈的位置标记为没有空位即可……
  
 
  
所以这个题最大的困难变成了求到底是第几个出圈的孩子会得到最多的糖果
  
这个时候有一个很神奇的东西出现了，他叫反素数：
  
 
对于反素数度娘的解释：
 
对于任何正整数x,其约数的个数记做g(x)（例如g(1)=1,g(6)=4.）
 
如果某个正整数x满足：对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数·
 
 
 
也就是说我们现在要求出小于总人数n最大的一个反素数
 
那么怎么求呢“？
 
首先，反素数有两个性质：
  
 
 
（1）一个反素数的所有质因子必然是从2开始的连续若干个质数，因为反素数是保证约数个数为的这个数尽量小
 
（2）同样的道理，如果，那么必有
 然后就可以搜索了，搜索打张表出来，线段树直接用…… 
 
 
 
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int fanprime[]={
    1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,  
    20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,  
    554400  
};  
  
int cnt[]={
    1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,  
    144,160,168,180,192,200,216  
};  

int tree[4 * 500005];  
struct ty  
{  
    char name[25];  
    int num;  
}a[500005];
int n, k;
void build(int p, int l, int r)  
{  
    tree[p] = r - l + 1;  
    if(r == l) return;  
    int mid = (l + r) /2;
    build (p * 2, l, mid); 
    build (p * 2 + 1, mid + 1, r); 
} 

int change(int p, int l, int r, int k)  
{  
    tree[p]--;  
    if(l == r)  return l;
    int mid = (l  + r)/ 2;  
    if(tree[p * 2] >= k) return change(p * 2, l, mid, k); 
    else return change(p * 2 + 1, mid + 1, r, k - tree[p * 2]); 
} 
int main()
{
	while(scanf("%d%d", &n, &k) != EOF)
	{  
        for(int i = 1; i <= n; i++)
			scanf("%s%d", a[i].name, &a[i].num);
		int t = 0;  
        while(fanprime[t] <= n) t++;
        t--;  
        build(1, 1, n);   
        int pos = 0;  
        a[pos].num = 0;  
        for(int i = 0; i < fanprime[t]; i++)  
        {  
            if(a[pos].num > 0)  
            {  
                k = ((k + a[pos].num - 2) % tree[1] + tree[1]) % tree[1] + 1;  
            }  
            else  
            {  
                k = ((k + a[pos].num - 1) % tree[1] + tree[1]) % tree[1] + 1;  
            }  
            pos = change(1, 1, n, k);  
        }  
         printf("%s %d\n", a[pos].name, cnt[t]);  
    }  
    return 0;
}