【POJ】2886 Who Gets the Most Candies?

移动题目相当麻烦。
 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define MAXN 500005
 5 #define lson l, mid, rt<<1
 6 #define rson mid+1, r, rt<<1|1
 7 
 8 int RPrime[] = {
 9     1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,
10     20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,MAXN
11 };
12 
13 int fact[] = {
14     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,
15     144,160,168,180,192,200
16 };
17 
18 typedef struct {
19     int l, r;
20     int sum;
21 } node_st;
22 
23 node_st nums[MAXN<<2];
24 char names[MAXN][11];
25 int val[MAXN];
26 
27 void build(int l, int r, int rt) {
28     int mid;
29 
30     nums[rt].sum = r - l + 1;
31     nums[rt].l = l;
32     nums[rt].r = r;
33     if (l == r) return;
34     mid = (l+r)>>1;
35     build(lson);
36     build(rson);
37 }
38 
39 int query(int k, int rt) {
40     nums[rt].sum--;
41     if (nums[rt].l == nums[rt].r)
42         return nums[rt].l;
43 
44     if (nums[rt<<1].sum >= k)
45         return query(k, rt<<1);
46     else {
47         k -= nums[rt<<1].sum;
48         return query(k, rt<<1|1);
49     }
50 }
51 
52 int main() {
53     int n, m, index;
54     int i, j, max;
55 
56     while (scanf("%d %d", &n, &m) != EOF) {
57         for (i=1; i<=n; ++i)
58             scanf("%s %d", names[i], &val[i]);
59         i = 0;
60         while (RPrime[i] <= n)
61             ++i;
62         j = RPrime[i-1];
63         max = fact[i-1];
64         build(1, n, 1);
65         --m;
66         for (i=1; i<=j; ++i) {
67             index = query(m+1, 1);
68             if (i == j)
69                 break;
70             --n;
71             if (val[index] > 0)
72                 m = (m+val[index]-1)%n;
73             else
74                 m = ((m+val[index])%n + n)%n;
75         }
76         printf("%s %d
", names[index], max);
77     }
78 
79     return 0;
80 }