1的位置，很容易发现1的位置是从1->2->4->8……如果超过数尾则从头偏移，总之只要经过若干次移动，1再次移动在1的位置，就能够保证洗牌洗回了原序列。
- 描述
-
设2n张牌分别标记为1，2，…，n，n+l，…，2n，初始时这2n张牌按其标号从小到大排列。
经一次洗牌后，原来的排列顺序变成n+l，l，n+2，2，··，，2n，n。
即前n张牌被放到偶数位置2，4，·，·，2n，而后n张牌被放到奇数位置1，3，…，2n-l。
可以证明对于任何一个自然数n，经过若干次洗牌后可恢复初始状态。
编程任务:对于给定的n的值(n<=24000)，编程计算最少经过多少次洗牌可恢复到初始状态。- 输入
- 由键盘输入n的值。
输入包含多组数据，每行一个整数N。 - 输出
- 程序运行结束时，将计算出的最少洗牌次数在屏幕上输出。
对于输入的N，输出最少需要的洗牌次数 - 样例输入
-
10
- 样例输出
-
6
洗牌问题：
定理1：当第一张牌(牌1)回到初始位置时，所有的牌都回到了初始位置。
证明：设有一次操作，某牌在操作前处于位置r(1<=r<=2*N)，那么，操作后，如果r原来是前一半的，显然r'=r*2; 否则，r'=(r-n)*2-1，即r'='r*2-(N*2+1);
将两个式子综合，可以得到r'= (r*2)%(N*2+1);
根据同余定理之一 ((i%m)*j)%m=(i*j)%M，可以整理出公式：i次操作后，该牌的位置为：
(r*(2^i))%(N*2+1);其中^表示乘方。
现在，我们假设经过M次操作后，牌1回到了初始位置，即(1*(2^M))%(N*2+1)=1时，再次应用同余定理，可以证明对于任意的k(1<=k<=2*N)，有(k*(2^M))%(N*2+1)=k，翻译成自然语言就是：当第一张牌回到初始位置时，所有的牌都回到了初始位置。命题得证。
定理2：一定存在某次操作M，这次操作后，所有的牌都回到了初始位置。
证明：我们已经证明了牌1回到初始位置时，所有的牌都回到初始位置，所以我们只需要证明牌1可以回到初始位置，即(2^M)%(N*2+1)=1一定有正整数解。证明这个定理前我们首先证明这样一个定理：
定理2.1：(2*r)%(2*n+1)==t
当t确定为1到2*n中的某值时(1<t<=2*n)，r在1到2*n间有唯一解
因为2*n+1是奇数，我们只要看一下就会发现r到t是一个一一映射，当t为偶数时，显然r=t/2，当t为奇数时，r=(t+1)/2+n，
现在我们来证明定理2。运用反正法，若牌1永远不能回到初始位置，根据鸽笼定理，牌1必然陷入了某个不包含位置1的循环，因为下一状态仅和当前状态有关，当前状态最多只有2*N种，所以显然一定在不超过2*N+1次操作内出现重复状态。而重复状态则意味着循环。
因为我们假设这一循环不包括位置1，我们设f(i)为循环中某状态，f(0)=1,f(n+1)=(f(n)*2)%(2*N+1)，f(j)为若干次循环后出现的重复状态，即f(i)=f(j)。因为循环一直持续，不妨假设j>i+i。又因为循环不包括状态1，即对于任意的k>=i，f(k)!=1
根据定理2.1，我们可以根据当前状态推出上一状态，换句话说，若f(i)=f(j)，则f(i-1)=f(j-1)。继续套用定理2.1，可以得到f(i-i)=f(j-i)，即：f(j-i)=f(0)=1。又有假设j>i+i，即j-i>i，与另一假设对于任意的k>=i，f(k)!=1矛盾。
因此，可以证明，牌1所陷入的循环，必然是包含位置1的，即一定有某次操作，操作后牌1回到了初始状态。而且显然的，初始状态就是这循环中的一个状态。
因此命题得证。
例如当n==4时，过程如下：
5 1 6 2 7 3 8 4
7 5 3 1 8 6 4 2
8 7 6 5 4 3 2 1
4 8 3 7 2 6 1 5
2 4 6 8 1 3 5 7
1 2 3 4 5 6 7 8
经过6次
超时程序，用于看结果：
/*
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext())
{
int number=scanner.nextInt();
int sum=1,i;
for(i=1;i<=2*number+1;i++)
{
sum*=2;
if(sum>2*number+1)
sum%=(2*number+1);
if(sum==1)break;
}
System.out.println(i);
}
}
}*/
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext())
{
int number=scanner.nextInt();
int result[]=new int[2*number+1];
for(int i=1;i<=2*number;i++)
{
result[i]=i;
}
int[] result1=new int[2*number+1];
int[] finalresult=new int[2*number+1];
for(int i=1;i<=2*number;i++)
{
finalresult[i]=result[i];
}
int sum=0;
while(true)
{
sum++;
int t=1;
for(int i=2;i<=2*number;i+=2)
{
result1[i]=result[t++];
}
t=1;
for(int i=1;i<=2*number;i+=2)
{
result1[i]=result[number+t++];
}
/*for(int i=1;i<=2*number;i++)
{
System.out.print(result1[i]+" ");
}
System.out.println();*/
int flag=1;
for(int i=1;i<=2*number;i++)
{
if(result1[i]!=finalresult[i])
{
flag=0;break;
}
}
for(int i=1;i<=2*number;i++)
{
result[i]=result1[i];
}
if(flag==1)break;
}
System.out.println(sum);
}
}
}
ac代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext())
{
int number=scanner.nextInt();
int sum=1,i;
for(i=1;i<=2*number+1;i++)
{
sum*=2;
if(sum>2*number+1)
sum%=2*number+1;
if(sum==1)break;
}
System.out.println(i);
}
}
}