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);
}
}