学步园

题意:

约瑟夫环,每次转移的步数根据跳出那个孩子手中牌的数字决定,可以有负数.

求第p个跳出的孩子的名字 以及p的约数个数

p为不大于n的最大反素数

反素数...制表..

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,l,h) for(int i=(l);i<=(h);++i)
#define FORD(i,h,l) for(int i=(h);i>=(l);--i)

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1 | 1

#define N 500010

int tree[N<<2];
const int antiprime[]={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,554400,665280};
const int factorNum[]={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,216,224};
struct child
{
	char name[15];
	int val;
}c[N];

void build(int l,int r,int rt)
{
	tree[rt]=r-l+1;//区间长度为键值,表示空余位置
	if(l==r)	return;
	int m=(l+r)>>1;
	build(lson);
	build(rson);
}
int update(int p,int l,int r,int rt)
{
	tree[rt]--;//一路减
	if(l==r)	return l;//返回找到的位置
	int m=(l+r)>>1;//这个位置是通过键值找到的,线段树就是在这里可以加速.像是二分,而且它可以集成
	if(p<=tree[rt<<1])	return update(p,lson);//存一段区间上的总和或最值
	return update(p-tree[rt<<1],rson);
}

int main(void)
{
	int n,k,&mod=tree[1];//mod是根节点的引用,代表剩余孩子的总数
	while(scanf("%d%d",&n,&k)==2)
	{
		FOR(i,1,n)	scanf("%s%d",c[i].name,&c[i].val);
		build(1,n,1);
		FOR(i,1,7)  cout<<tree[i]<<" ";
		cout<<endl;
		int cnt=0;
		while(cnt<35 && antiprime[cnt]<=n)	cnt++;
		cnt--;
		int pos=0;
		c[pos].val=0;
		REP(i,antiprime[cnt])//antiprime[cnt]即p
		{///添加与删除等价!!!
			if(c[pos].val>0)
            {//各种取模其实是为了凑数啊...
                k=((k+c[pos].val-2)%mod+mod)%mod+1;
                cout<<endl;
            }
			else	//涉及到循环必用取模
			{//既可以理解成他前面的位置是不变的,又可以理解成mod减少了1(他自己不在了,所以mod用mod+1替代)
			    k=((k+c[pos].val-1)%mod+mod)%mod+1;
                cout<<endl;
			}
			pos=update(k,1,n,1);
		}//如果用数组直接模拟的话,这个孩子还在不在总是要访问一下才知道,所以复杂度O(n^2)(等差数列求和1..n-1)
		//用线段树模拟时,总能够避开已经占用的位置.
		//线段树中的pos按照剩下的孩子原先的编号重新排序.所以仍然是找到前面有多少空位置之后的那个.!
		printf("%s %d\n",c[pos].name,factorNum[cnt]);
	}
	return 0;
}