hdu1210Eddy's 洗牌问题

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1210

Eddy是个ACMer,他不仅喜欢做ACM题,而且对于纸牌也有一定的研究,他在无聊时研究发现,如

果他有2N张牌，编号为1,,..n,n+,..2n。这也是最初的牌的顺序。通过一次洗牌可以把牌

的序列变为n+,,n+,,n+,,n+,..2n,n。那么可以证明，对于任意自然数N，都可以

在经过M次洗牌后第一次重新得到初始的顺序。编程对于小于100000的自然数N，求出M的

值。

　　首先从数据范围来看暴力模拟是很麻烦并且会超时的，手动跑几个数据我们就会发现一次牌洗到初始序列的过程中每一次的序列都是各不相同的，每一个数的位置也不会重复，所以我们只看1的位置，而从第一次洗牌我们可以发现，初始在1到n位置的数，一次洗牌之后就到了相应位置*2的位置（因为每个数前面都插了一张牌），而后面n个数则插到了前面，变成了1 3 5 7 9，，，也就是（位置-n）*2-1的位置，所以只需要一个循环找1的位置，当1再次回到位置1的时候，就把牌又洗出来。

代码：

 #include<iostream>

 #include<cstdio>

 using namespace std;

 int n;

 int ans;

 int pos;

 int main()

 {

     while(scanf("%d",&n)!=EOF)

     {

         ans=,pos=;

         while(pos!=)

         {

             if(pos<=n)pos*=,ans++;

             else pos=(pos-n)*-,ans++;

         }

         printf("%d\n",ans);

     }

     return ;

 }

qwq还是要多多思考啊

巴特西

hdu1210Eddy's 洗牌问题

最新文章

热门文章