POJ 2886 Who Gets the Most Candies? (高合成数&用线段树维护约瑟夫环)

http://poj.org/problem?id=2886

思路：

题目要求约数个数最大的数，此即高合成数的定义（也有人把它叫做反素数，但这种叫法是错的，实际上的反素数是指一个数及其回文数都是素数）。

wiki：http://en.wikipedia.org/wiki/Highly_composite_number

OEIS：http://oeis.org/A002182

然后就是用线段树维护约瑟夫环中剩余孩子的个数了，即维护[1,p]范围内的孩子个数。

最后是计算下一个位置，做法如下：

if (card[id] > 0) /// 正方向移动，由于后面的孩子受到第k个孩子跳出的影响，位置要-1才能保证序列“连续”
	k = (k - 1 + card[id] - 1) % m + 1; /// k指的是给未出去孩子编号后的第k号，后面的-1+1是为了确保结果在[1,m]上
else
	k = ((k + card[id] - 1) % m + m) % m + 1;
           

完整代码：

/*985ms,11848KB*/

#include<cstdio>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define root 1, n, 1
const int mx = 500005;
const int hcn[] = {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, mx};
const int factor[] = {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};

int leftcnt[mx << 2];
char name[mx][11];
int card[mx];

void build(int l, int r, int rt)
{
	leftcnt[rt] = r - l + 1;
	if (l == r) return;
	int m = (l + r) >> 1;
	build(lson);
	build(rson);
}

int query(int p, int l, int r, int rt)
{
	--leftcnt[rt];
	if (l == r) return l;
	int m = (l + r) >> 1;
	if (p <= leftcnt[rt << 1]) return query(p, lson);
	else return query(p - leftcnt[rt << 1], rson);
}

int main()
{
	int n, m, k, times, maxcandy, i, id;
	while (~scanf("%d%d", &n, &k))
	{
		i = 0;
		while (hcn[i] <= n) ++i;
		--i;
		times = hcn[i];
		maxcandy = factor[i];
		build(root);
		for (i = 1; i <= n; i++) scanf("%s%d", name[i], &card[i]);
		m = n;
		while (times--)
		{
			id = query(k, root);
			if (--m == 0) break; /// 刚好到最后一个孩子了
			if (card[id] > 0) /// 正方向移动，由于后面的孩子受到第k个孩子跳出的影响，位置要-1才能保证序列“连续”
				k = (k - 1 + card[id] - 1) % m + 1; /// k指的是给未出去孩子编号后的第k号
			else
				k = ((k + card[id] - 1) % m + m) % m + 1;
		}
		printf("%s %d\n", name[id], maxcandy);
	}
}