杭電1210 Eddy's 洗牌問題

Eddy's 洗牌問題

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 4131    Accepted Submission(s): 2752

Problem Description Eddy是個ACMer,他不僅喜歡做ACM題,而且對于紙牌也有一定的研究,他在無聊時研究發現,如果他有2N張牌，編号為1,2,3..n,n+1,..2n。這也是最初的牌的順序。通過一次洗牌可以把牌的序列變為n+1,1,n+2,2,n+3,3,n+4,4..2n,n。那麼可以證明，對于任意自然數N，都可以在經過M次洗牌後第一次重新得到初始的順序。程式設計對于小于100000的自然數N，求出M的值。

Input 每行一個整數N  

Output 輸出與之對應的M  

Sample Input

20
1
        

Sample Output

20
2
        

Author Eddy  

Source 杭電ACM省賽集訓隊選拔賽之熱身賽  

Recommend Eddy   |   We have carefully selected several similar problems for you:   1214  1211  1207  1204  1221 

模拟題，直接根據所給提示模拟，附代碼：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[110000*2],i,j,k,l,m,b[110000*2]; 
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int flag=1;
		int cnt=0;//如果1第二次回到了第一個的位置 ，那麼代表1次循環 
		while(1)
		{
			if(flag==1&&cnt)//洗牌成功 
			{
				printf("%d\n",cnt);
				break;
			}
			if(flag<=n)
			flag*=2;
			else
			{
				flag-=n;
				flag*=2;
				flag-=1;
			}
			cnt++;
		}
	}
}