poj1012——Joseph

44424742

约瑟夫环问题。
其中的注释部分为暴力方法，这明显会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;}