POJ 2886 Who Gets the Most Candies? 反素数+线段树

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <climits>

using namespace std;

typedef long long LL;

const int maxn = 500000 + 5;
int sum[maxn << 2];

//线段树

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
void build(int rt,int l,int r) {
    if(l == r) sum[rt] = 1;
    else {
        int mid = (l + r) >> 1;
        build(lson); build(rson);
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    }
}

void update(int rt,int l,int r,int tar,int x) {
    if(l == r) sum[rt] = x;
    else {
        int mid = (l + r) >> 1;
        if(tar <= mid) update(lson,tar,x);
        else update(rson,tar,x);
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    }
}

int query(int rt,int l,int r,int v) {
    if(l == r) return l;
    else {
        int mid = (l + r) >> 1,lc = rt<<1,rc = lc + 1;
        if(sum[lc] >= v) return query(lson,v);
        else return query(rson,v - sum[lc]);
    }
}

//反素数生成
int prime[20] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};
int minv[maxn],times[40];
void dfs(LL arr,int nowcnt,int nowt,LL lim) {
    if(arr > lim) return;
    //cout << arr << " " << nowcnt << " " << nowt << " " << lim << endl;
    minv[nowcnt] = min(minv[nowcnt],(int)arr);
    for(int i = 1;nowt == 0 || i <= times[nowt - 1];i++) {
        arr *= prime[nowt];
        if(arr > lim) break;
        nowcnt = nowcnt / i * (i + 1);
        times[nowt] = i;
        dfs(arr,nowcnt,nowt + 1,lim);
    }
}

char name[maxn][20];
int k[maxn],N,K;

void solve() {
    int nowpos = K,ans,ansv,nowk,pos = K;
    build(1,1,N);
    for(int i = 1;i <= N;i++)
        if(minv[i] <= N) ansv = i;
    for(int i = 1;i <= N;i++) {
        pos = query(1,1,N,nowpos);
        update(1,1,N,pos,0);
  //      printf("%d:%s out in %d\n",pos,name[pos],i);
        nowk = k[pos];
        if(i == minv[ansv]) {
            ans = pos; break;
        }
        if(nowk > 0) nowpos = ((nowpos + nowk - 2) % (N - i) + (N - i)) % (N - i) + 1;
        else nowpos = ((nowpos + nowk - 1) % (N - i) + (N - i)) % (N - i) + 1;
    }
    printf("%s %d\n",name[ans],ansv);
}

void setfile() {
    freopen("in.txt","r",stdin);
    freopen("a.txt","w",stdout);
}

int main() {
//    setfile();
    for(int i = 1;i <= maxn;i++) minv[i] = INT_MAX;
    dfs(1,1,0,maxn);
    while(scanf("%d%d",&N,&K) != EOF) {
        for(int i = 1;i <= N;i++) scanf("%s%d",name[i],&k[i]);
        solve();
    }
    return 0;
}