ZCMU--1720: 死亡如风，我要装逼

Description

死亡如风，我要装逼——哈撒给！！！大家好，我叫张全蛋，刚从qd旅游回来。然后。。。穷的连衣服都被人扒了。因为我当时点了一道海鲜。帝企鹅,the king of QQ 。其实当时还有许多和我一起去的游客也都被****。店主非常残忍。让我们n个人围成一个圈，每个人一个编号1,2,3...n.第一次从1开始数到（2^1）次辣个人就会被****，接下来从被****的下一个人重新开始计数,数到(2^2)次的辣个人就会被****.以此类推，第i次将会是数到第（2^i）次的人被****.最后的2个人可以幸免于难。然后我就这样回来了。

Input

多组测试数据

输入一个数n（2<=n<=10000）

Output

输出最后两个人的号码，a,b（a<b）。

Sample Input

2 

3

Sample Output

1  2

1  3

解析：用vector十分方便，因为erase可以直接删淘汰人的位置，留下来的数组中都是活着的，然后每次只要通过等式就可以直接找到下一个要淘汰的人的下标。至于题目中的（2^i）得用快速幂来计算，计算的同时取模的数其实就是场上活着的人数。

#include <stdio.h>
#include <vector>
using namespace std;
vector<int> v;
int k;
int qm(int b,int p){
	int r=1,l=v.size();	//l是场上人数 
	while(p){
		if(p%2==1) r=r*b%l;
		b=b*b%l;
		p/=2;
	}
	if(r+k-1<0) return v.size()-1;//特判一下，这种淘汰的刚好是最后一个人 
	return (r+k-1)%l;
}
int main()
{
	int n,i,p;
	while(~scanf("%d",&n)){
		v.erase(v.begin(),v.end());	//初始化情况 
		for(i=1;i<=n;i++) v.push_back(i);//输入人物编号 
		i=1,k=0;
		while(v.size()>2){
			p=qm(2,i);
			k=p;	//特别注意：从下一个人开始报数，也就是场上第k个人 
			v.erase(v.begin()+p);
			i++;
		}	
		printf("%d %d\n",v[0],v[1]);
	}
	return 0;
}