这道题综合性挺强的，又牵扯到数论，又有线段树。
线段树维护的信息就是区间中有多少个人没跳出去，然后计算出下一个人是剩下的人中第几个。
我在这调程序调了好久，就是那个模来模去的弄得我头晕。
不过题确实是好题，给赞。
1 #include <cstdio> 2 #include <iostream> 3 #include <cmath> 4 #include <string> 5 #include <algorithm> 6 #include <vector> 7 using namespace std; 8 9 const int maxn = 500000 + 10; 10 int n, k; 11 int sum[maxn << 2]; 12 13 void build(int o, int L, int R) 14 { 15 if(L == R) { sum[o] = 1; return; } 16 int M = (L + R) / 2; 17 build(o*2, L, M); 18 build(o*2+1, M+1, R); 19 sum[o] = sum[o*2] + sum[o*2+1]; 20 } 21 22 int update(int o, int L, int R, int p) 23 { 24 if(L == R) { sum[o] = 0; return L; } 25 int M = (L + R) / 2; 26 int ans; 27 if(sum[o*2] >= p) ans = update(o*2, L, M, p); 28 else ans = update(o*2+1, M+1, R, p-sum[o*2]); 29 sum[o] = sum[o*2] + sum[o*2+1]; 30 return ans; 31 } 32 33 const int maxp = 750; 34 int prime[maxp], pcnt = 0; 35 bool vis[maxp]; 36 37 void prime_table() 38 { 39 int m = sqrt(maxp); 40 for(int i = 2; i <= m; i++) if(!vis[i]) 41 for(int j = i * i; j < maxp; j += i) vis[j] = true; 42 for(int i = 2; i < maxp; i++) if(!vis[i]) prime[pcnt++] = i; 43 } 44 45 int F(int n) 46 { 47 int ans = 1; 48 for(int i = 0; i < pcnt && n > 1; i++) if(n % prime[i] == 0) 49 { 50 int c = 0; 51 while(n % prime[i] == 0) { n /= prime[i]; c++; } 52 ans *= c + 1; 53 } 54 if(n > 1) ans <<= 1; 55 return ans; 56 } 57 58 int next[maxn]; 59 char stu[maxn][11]; 60 61 int main() 62 { 63 //freopen("in.txt", "r", stdin); 64 65 prime_table(); 66 67 while(scanf("%d%d", &n, &k) == 2) 68 { 69 build(1, 0, n - 1); 70 int _max = 0, id; 71 for(int i = 0; i < n; i++) { scanf("%s%d", stu[i], &next[i]); } 72 73 int pos = k - 1; 74 for(int i = 1; i <= n; i++) 75 { 76 int t = update(1, 0, n - 1, pos + 1); 77 int f = F(i); 78 if(f > _max) 79 { 80 _max = f; 81 id = t; 82 } 83 if(i == n) break; 84 int MOD = n - i; 85 if(next[t] < 0) next[t]++; //负数的情况还要有一点小改动，在这坑了好久 86 pos = (((pos + next[t] - 1) % MOD) + MOD) % MOD; 87 } 88 printf("%s %d ", stu[id], _max); 89 } 90 91 return 0; 92 }