poj1012——Joseph

约瑟夫环问题。

其中的注释部分为暴力方法，这明显会tle。

so 参考：http://hi.baidu.com/autogerk/blog/item/3ec31065699e6df9f636546e.html

这篇也很有意思：http://www.9php.com/FAQ/cxsjl/c/2007/03/403506277877.html

#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
//bool vis[20];
int arr[15];
//bool solve(int n,int k)
//{
//	memset(vis,true,sizeof(vis));
//	int cout=0;int i=0,j=0;
//	while(cout<n/2)
//	{
//		i=i%n;
//		if(vis[i])
//		{
//			j++;
//			if(i>=n/2&&j==k)
//			{
//				cout++; 
//				if(cout==n/2 )return true;
//				j=0; vis[i]=false;
//			}
//			else if(j==k&&i<n/2) return false;
//		
//		}	i++;
//	}
//	return false;
//}
//int f(int n)
//{
//	int i;
//	for(i=2;;i++)
//	{
//		if(solve(n,i))
//		{
//			return i;
//		}
//	}
//}
void solve(int n)
{
	int len=n*2;
	int s,m=n+1;
	while(1)
	{
		s=0;
		int cout=0;
		while(cout<n)
		{
			int k=(s+m-1)%len;
			if(k>=n)
			{
				cout++;
				if(cout==n) 
				{
					arr[n]=m;
					printf("%d\n",m);
					return ;
				}
				s=k;
				len--;
			}
			else 
			{
				m++;
				s=0;len=n*2;
				break;
			}
		}
	}
}
int main()
{
	int n;
	memset(arr,0,sizeof(arr));
	while(1 )
	{
		cin>>n;
		if(n==0) break;
		if(arr[n])
			printf("%d\n",arr[n]);
		else solve(n);
	}
	return 0;
}