poj2886--Who Gets the Most Candies?(线段树+反素数)

题目链接点击打开链接

题目大意：给出n个人的姓名和手里的一个号码，n个人排成一圈，号码有正有负，代表着正向还是反向移动k个位置，比赛从第k个人开始，把被选到的人踢出，问按踢出的顺序中因子数最多的是谁？

建立线段树，把n个人被踢的顺序找到，然后求出n个人中因子数最多的（最小的数）是谁，这里要用到反素数，详看链接点击打开链接

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define root 1,n,1
#define int_rt int l,int r,int rt
int a[8] = {2,3,5,7,11,13,17,19} ;
int cl[2010000] ;
char str[510000][12] ;
int p[510000] , w[510000] , cnt ;
int n , ans , best ;
void push_up(int rt) {
    cl[rt] = cl[rt<<1] + cl[rt<<1|1] ;
}
void creat(int_rt) {
    if( l == r ) cl[rt] = 1 ;
    else {
        creat(lson) ;
        creat(rson) ;
        push_up(rt) ;
    }
}
int update(int k,int_rt) {
    if( l == r ) {
        cl[rt] = 0 ;
        return l ;
    }
    if( cl[rt<<1] >= k )
        k = update(k,lson) ;
    else
        k = update(k-cl[rt<<1],rson) ;
    push_up(rt) ;
    return k ;
}
void dfs(int dept,int temp,int num) {
    if( dept >= 8 ) return ;
    if( num > best ) {
        best = num ;
        ans = temp ;
    }
    if( num == best && temp < ans ) ans = temp ;
    for(int i = 1 ; i < 25 ; i++) {
        if( n/a[dept] < temp ) break ;
        temp *= a[dept] ;
        dfs(dept+1,temp,num*(i+1)) ;
    }
}
int main() {
    int m , k , i ;
    while( scanf("%d %d", &n, &k) != EOF ) {
        for(i = 1 ; i <= n ; i++) {
            scanf("%s %d", str[i], &p[i]) ;
        }
        creat(root) ;
        cnt = 1 ;
        while( 1 ) {
            m = update(k,root) ;
            w[m] = cnt++ ;
            if( !cl[1] ) break ;
            if( p[m] >= 0 ) {
                k = (k+p[m]-1)%cl[1] ;
                if( !k ) k = cl[1] ;
            }
            else {
                k = (k-cl[1]-1+p[m])%cl[1] ;
                if( !k ) k = 1 ;
                else k = cl[1]+1+k ;
            }
        }
        best = 0 ;
        ans = n ;
        dfs(0,1,1) ;
        for(i = 1 ; i <= n ; i++){
            if( w[i] == ans ) {
                printf("%s %d\n", str[i], best) ;
                break ;
            }
        }
    }
    return 0;
}