多组测试数据
给定人数与初始位置
名字与指针
环状内每个人出列后，指向位置的人出列，重复此过程。
输出出列次序的因数最大的那个人的名字及因子数
最后的tie应该是平局的意思吧
线段树单点修改
注意出列时总人数减少，每个点对应位置减少（这也是需要使用线段树或者树状数组的原因），求余的时候应该是对小于mod的数进行操作
1 #include2 #include 3 #include 4 #include 5 #include 6 #define max(x, y) (x > y ? x : y) 7 #define min(x, y) (x > y ? y : x) 8 #define INF 0x3f3f3f3f 9 #define mod 100000000710 #define Yes printf("Yes\n")11 #define No printf("No\n")12 typedef long long LL;13 using namespace std;14 15 const int maxn = 5e5 + 5;16 17 int fac[maxn];18 int n, n_, k;19 int dir[maxn];20 int pos, candies;21 char name[maxn][12];22 23 struct node {24 int l, r, n;25 }a[maxn * 4];26 27 void factor() {28 fill(fac, fac + maxn, 1);29 for (int i = 2; i < maxn; i++) {30 if (fac[i] == 1) {31 for (int j = i; j < maxn; j += i) {32 int k = 1, m = j;33 while (m % i == 0) {34 m /= i;35 k++;36 }37 fac[j] *= k;38 }39 }40 }41 }42 43 void init() {44 n_ = 1;45 while (n_ < n) n_ *= 2;46 for (int i = n_; i < 2 * n_; i++) {47 a[i].l = a[i].r = i - n_ + 1;48 a[i].n = 1;49 }50 for (int i = n_ - 1; i > 0; i--) {51 a[i].l = a[2 * i].l;52 a[i].r = a[2 * i + 1].r;53 a[i].n = a[i].r - a[i].l + 1;54 }55 pos = 1, candies = -INF;56 for (int i = 1; i <= n; i++) {57 if (fac[i] > candies) {58 pos = i;59 candies = fac[pos];60 }61 }62 63 }64 65 int out_(int i, int p) {66 a[i].n--;67 if (a[i].l == a[i].r) return a[i].l;68 if (a[2 * i].n >= p) {69 return out_(2 * i, p);70 } else {71 return out_(2 * i + 1, p - a[2 * i].n);72 }73 }74 75 int main(int argc, const char * argv[]) {76 factor();77 while (~scanf("%d%d", &n, &k)) {78 init();79 for (int i = 1; i <= n; i++) {80 scanf("%s %d", name[i], &dir[i]);81 }82 83 int p = 1;84 while (pos--) {85 n--;86 p = out_(1, k);87 if (!n) break;88 if (dir[p] >= 0) {89 k = (k - 1 + dir[p] - 1) % n + 1;90 } else {91 k = ((k + dir[p] - 1) % n + n) % n + 1;92 }93 }94 printf("%s %d\n", name[p], candies);95 }96 return 0;97 }