# POJ - 2886 Who Gets the Most Candies?树状数组 + 二分 + 反素数

xiaoxiao2021-02-28  48

数，都有，那么称为反素数。

#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #define ll long long #define pb push_back #define fi first #define se second #define pi acos(-1) #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define rep(i,x,n) for(int i=x;i<n;i++) #define per(i,n,x) for(int i=n;i>=x;i--) using namespace std; typedef pair<int,int>P; const int MAXN = 500010; const int MAXM = 1010; int gcd(int a,int b){return b?gcd(b,a%b):a;} int prime[MAXN]; bool isprime[MAXM]; int num = 0; P anti_prime[MAXM]; void dfs(int fac_num, int val, int pos, int limit) { if(val > MAXN) return ; anti_prime[num++] = P(val, fac_num); int tmp = val; for(int i = 1; i <= limit && tmp < MAXN; i++) { tmp *= prime[pos]; dfs(fac_num * (i + 1), tmp, pos + 1, i); } } void init() { // get prime int cnt = 0; memset(isprime, 1, sizeof(prime)); isprime[1] = 0; for(int i = 2; i < MAXM; i++) { if(isprime[i]) { prime[cnt++] = i; for(int j = i + i; j < MAXM; j += i) isprime[j] = 0; } } // get antiprime num = 0; dfs(1, 1, 0, 20); sort(anti_prime, anti_prime + num); } int bit[MAXN]; int sum(int i) { int res = 0; while(i) { res += bit[i]; i -= -i & i; } return res; } void add(int i, int delta) { while(i < MAXN) { bit[i] += delta; i += i & -i; } } int bi_search(int val) { int l = 0, r = MAXN, mid; while(l <= r) { mid = (l + r) >> 1; if(sum(mid) >= val) r = mid - 1; else l = mid + 1; } return r + 1; } char name[MAXN][15]; int card[MAXN]; int main() { int n, k; init(); //cout << num << endl; //for(int i = 0; i < num; i++) //printf("%d %d\n", anti_prime[i].fi, anti_prime[i].se); while(cin >> n >> k) { memset(bit, 0, sizeof(bit)); for(int i = 1; i <= n; i++) { scanf(" %s %d", name[i], card + i); add(i, 1); } int up = 0, ans = 0; for(int i = 0; i < num; i++) { if(anti_prime[i].fi > n) break; if(anti_prime[i].se > ans) up = anti_prime[i].fi, ans = anti_prime[i].se; } int now = k, nxt = k; for(int i = 1; i < up; i++) { add(now, -1);//将小朋友出队 int m = n - i; int x = card[now]; if(x > 0)//计算下一个要出队小朋友在当前序列的位置 nxt = (nxt - 1 + x) % m; else nxt = ((nxt + x) % m + m) % m; if(nxt == 0) nxt = m; //printf("%d %s\n", now, name[now]); now = bi_search(nxt);//得到下一个要出队的小朋友在原序列的位置 //printf("%d %d %d\n", now, nxt, m); } printf("%s %d\n", name[now], ans); } return 0; }