POJ 2886: Who Gets the Most Candies?

POJ100問AC記念．

概要

N人の子供が一枚ずつカードを持っていて，輪になって並んでいる．
K番目の子供からスタートする．まず，現在選んでいる子供を輪から除外する．除外した子供が持っていたカードに書かれている番号だけずれた子供を選ぶ．これを繰り返す．
i番目の操作で除外された子供は，iの約数の数だけキャンディをもらえる．
一番多くキャンディをもらえる子供は誰か．

解法

約数の個数は篩みたいにするとうまく計算できる．
子供を除外してずれる番号は，BITをうまく利用して管理する．
次に選ぶ子供はBIT上で二分探索をして求めることができる．

注意

同じ個数を得る子供は，先に輪の外に出た方を出力．
カードの番号が負の時の扱いに注意

const int MN = 500010;

int N, K;
int A[500010];
char name[500010][16];
int bit[500010];
bool isPrime[500010];
ll F[500010];

void update(int i, int v){
	++i;
	while(i <= N){
		bit[i] += v;
		i += i & -i;
	}
}
int get(int i){
	++i;
	int res = 0;
	while(i>0){
		res += bit[i];
		i -= i & -i;
	}
	return res;
}
int find(int num){
	int lb = -1, ub = N;
	while(ub - lb > 1){
		int mid = (ub + lb) / 2;
		if(get(mid)-1 < num){
			lb = mid;
		}
		else{
			ub = mid;
		}
	}
	return ub;
}
void solve(){
	memset(bit, 0, sizeof(bit));
	for(int i=0;i<N;++i)update(i,1);
	int mx = 0, ridx = 0, idx = --K;

	for(int k=0;k<N;++k){
		if(F[k+1] > mx){
			mx = F[k+1];
			ridx = idx;
		}
		update(idx, -1);
		if(k == N - 1) break;
		int num = N - k - 1;
		if(A[idx] > 0){
			K = (K + A[idx] - 1) % num;
		}else{
			K = (K + A[idx]) % num;
		}
		if(K < 0) K += num;
		idx = find(K);
	}
	printf("%s %d\n", name[ridx], mx);
}
main(){
    for(int i = 0; i < MN; ++i) F[i] = 1;
    for(int i = 2; i < MN; ++i) if(!isPrime[i]){
		for(int j = i; j < MN; j += i){
			int k = 0;
			for(int l=j; l % i == 0; l /= i, ++k);
			isPrime[j] = true;
			F[j] *= k + 1;
		}
    }
	while(~scanf("%d%d", &N, &K)){
		for(int i=0;i<N;++i){
			scanf("%s%d", name+i, A+i);
		}
		solve();
	}
	return 0;
}