Zcmu--1720: death is like the wind, I want to pretend to force

Description

The wind of death , I want to pretend to force —— Hassa gave ！！！ Hello everyone , My name is Zhang quandan , Just from qd Travel back . then ... Poor people even got their clothes picked . Because I ordered a seafood . emperor penguin ,the king of QQ . In fact, many tourists who went with me were also ****. The shopkeeper is very cruel . Let us n A circle of individuals , Each person has a number 1,2,3...n. First time from 1 Start counting to （2^1） The second spicy person will be ****, Next, from being **** The next person starts counting again , Count to (2^2) The second spicy person will be ****. And so on , The first i Times will be counted to （2^i） The second person was ****. final 2 Individuals can survive . Then I came back like this .

Input

Multiple sets of test data

Enter a number n（2<=n<=10000）

Output

Output the numbers of the last two people ,a,b（a<b）.

Sample Input

2 

3

Sample Output

1  2

1  3

analysis ： use vector It is very convenient , because erase You can directly delete the position of the eliminated person , All the remaining arrays are alive , Then every time you just pass the equation, you can directly find the subscript of the next person to be eliminated . As for the question （2^i） We have to use the fast power to calculate , The number of modulos taken while calculating is actually the number of people alive on the field .

#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 It's the number of people on the court  
	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;// It's a special verdict , This kind of elimination happens to be the last person  
	return (r+k-1)%l;
}
int main()
{
	int n,i,p;
	while(~scanf("%d",&n)){
		v.erase(v.begin(),v.end());	// Initialization situation  
		for(i=1;i<=n;i++) v.push_back(i);// Enter the person number  
		i=1,k=0;
		while(v.size()>2){
			p=qm(2,i);
			k=p;	// Particular attention ： Count off from the next person , That is, the first on the court k personal  
			v.erase(v.begin()+p);
			i++;
		}	
		printf("%d %d\n",v[0],v[1]);
	}
	return 0;
}