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;
}