poj2886

线段树+反素数。这题是类似于约瑟夫环的问题。

首先我们得了解反素数，我们有n 个人，那么就至少有n个回合，要求第几个出局的人获得的糖果最多(获得的糖果数等于第i轮出局的人，i所含的因子的个数)，而反素数的定义就是对于一个数字x,有任意一个i(0< i < x),都有g(x)>g(i) (g(x)代表x所含的因子的个数)，所以对于1-n来说，含有因子的数目最多，又得是最多里面数字最小的，那么只有那个最接近n的反素数了。比如n=8，那么最接近n的反素数就是6，6和8都有最多的四个因子，但是6更小。

前50w的反素数有

int ip[] = {1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720,

840, 1260, 1680, 2520, 5040, 7560, 10080, 15120, 20160,

25200, 27720, 45360, 50400, 55440, 83160, 110880,

166320, 221760, 277200, 332640, 498960, 500001

}; //反素数

它们所含的因子的个数为：

int div1[] = {1, 2, 3, 4, 6, 8, 9, 10, 12, 16, 18, 20, 24, 30, 32, 36,

40, 48, 60, 64, 72, 80, 84, 90, 96, 100, 108, 120,

128, 144, 160, 168, 180, 192, 200

};//反素数对应的约数个数

接下去就是模拟那个类似约瑟夫环的过程，直接模拟肯定是不行的，此时我们就想到用线段树来实现单点更新，求的那个最接近n的反素数，我们假设为m,则我们模拟m遍即可。

#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<time.h>
#include<queue>
#include<stack>
#include<iterator>
#include<math.h>
#include<stdlib.h>
#include<limits.h>
#include<map>
#include<set>
#include<bitset>
//#define ONLINE_JUDGE
#define eps 1e-8
#define INF 0x7fffffff
#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define sfs(a) scanf("%s",a)
#define sf(a) scanf("%d",&a)
#define sfI(a) scanf("%I64d",&a)
#define pf(a) printf("%d\n",a)
#define pfI(a) printf("%I64d\n",a)
#define pfs(a) printf("%s\n",a)
#define sfd(a,b) scanf("%d%d",&a,&b)
#define sft(a,b,num) scanf("%d%d%d",&a,&b,&num)
#define for1(i,a,b) for(int i=(a);i<b;i++)
#define for2(i,a,b) for(int i=(a);i<=b;i++)
#define for3(i,a,b)for(int i=(b);i>=a;i--)
#define MEM1(a) memset(a,0,sizeof(a))
#define MEM2(a) memset(a,-1,sizeof(a))
#define ll long long
const double PI = acos(-1.0);
template<class T> T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;}
template<class T> T lcm(T a, T b) {
    return a / gcd(a, b) * b;}
template<class T> inline T Min(T a, T b) {
    return a < b ? a : b;}
template<class T> inline T Max(T a, T b) {
    return a > b ? a : b;}
using namespace std;
#define M 500010
int n,m,k;
struct Peo{
    char name[15];
    int val;
}a[M];
int tree[M*4];
int ip[] = {1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720,
            840, 1260, 1680, 2520, 5040, 7560, 10080, 15120, 20160,
            25200, 27720, 45360, 50400, 55440, 83160, 110880,
            166320, 221760, 277200, 332640, 498960, 500001
           }; //反素数

int div1[] = {1, 2, 3, 4, 6, 8, 9, 10, 12, 16, 18, 20, 24, 30, 32, 36,
             40, 48, 60, 64, 72, 80, 84, 90, 96, 100, 108, 120,
             128, 144, 160, 168, 180, 192, 200
            };//反素数对应的约数个数
void pushUp(int p){                 //更新区间所在的父节点
    tree[p] = tree[p<<1]+tree[p<<1|1];
}
void build(int p,int s,int e){      //建树
    if(s == e){
        tree[p] = 1;
        return;
    }
    int mid = (s+e)>>1;
    build(p<<1,s,mid);
    build(p<<1|1,mid+1,e);
    pushUp(p);
}
int upDate(int p,int s,int e,int x){
    if(s == e){
        tree[p] = 0;
        return s;
    }
    int mid = (s+e)>>1;
    int res;
    if(x<=tree[p<<1])
        res = upDate(p<<1,s,mid,x); //左子树的第x个节点
    else
        res = upDate(p<<1|1,mid+1,e,x-tree[p<<1]);  //右子树的第x-tree[p<<1]个节点
    pushUp(p);      //更新父节点
    return res;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
//      freopen("out.txt", "w", stdout);
#endif
    while(sfd(n,k)!=EOF){
        memset(tree,0,sizeof tree);
        for(int i=1;i<=n;i++)
            scanf("%s%d",a[i].name,&a[i].val);
        build(1,1,n);
        int ans;
        for(int i=0;ip[i]<=n;i++){      //m为最接近n的反素数,ans为其所含的因子的个数
            m = ip[i];
            ans = div1[i];
        }
        int res = n;
        int pos;
        for(int i=0;i<m;i++){
            res--;
            pos = upDate(1,1,n,k);
            if(res == 0) break;         //注意 下面res的取余时,res不能为0啊，所以得提前break掉
            if(a[pos].val>=0)
                k = (k-1+a[pos].val-1)%res+1;       //计算k左边的第a[pos].val个
            else
                k = ((k-1+a[pos].val)%res+res)%res+1;   //计算k右边的第a[pos].val个
        }
        printf("%s %d\n",a[pos].name,ans);
    }
    return 0;
}