【问题描述】
设 2n 张牌分别标记为 1, 2, ..., n, n+1, ..., 2n，初始时这 2n 张牌按其标号从小到大
排列。经一次洗牌后，原来的排列顺序变成 n+1, 1, n+2, 2, ..., 2n, n。即前 n 张牌被放到
偶数位置 2, 4, ..., 2n，而后 n 张牌被放到奇数位置 1, 3, ..., 2n-1。可以证明对于任何一
个自然数 n，经过若干次洗牌后可恢复初始状态。现在你的的任务是计算对于给定的 n 的值(n≤10 5 )，
最少需要经过多少次洗牌可恢复到初始状态。
【输入】
输入仅有一个整数，表示 n 的值。
【输出】
输出仅一行包含一个整数，即最少洗牌次数。
【输入样例】
10
【输出样例】
6
【分析】
（讨论过程可见此贴：http://tieba.baidu.com/p/3246473319）
手写几组小的数据可以发现，只要数字1 回到它的初始位置，那么整个序列就会恢复成初始状态。然后无脑模拟 1 的位置变化。
但是，为什么？
最开始的想法是「只要有一个数字回到原位，整个序列就会回到初始状态」。然后找到了反例，比如当 n=10 时，数字 1 的轨迹为：
1 -> 2 -> 4 -> 8 -> 16 -> 11 -> 1
而数字 3 的轨迹为：
3 -> 6 -> 12 -> 3
当数字 3 回到原位时整个序列并没有复原。
所以，只能追踪数字 1 的位置来判断整个序列的状态。
【证明】
法一：
设 1 经过 t 次回到原位，则 2t ≡ 1 (mod 2n+1)，由此推出
2t *x ≡ x (mod 2n+1)
即每张牌都回到了原位。
法二：
首先，我们可以发现对于每张牌的移动规律可以用一个式子概括：
x -> 2x mod (2n+1) -> 4x mod (2n+1) -> ...
那么，我们的目的就是求出一个最小的 t，使得
对于任意的 x∈[1, 2n] 都有 2tx mod (2n+1) = x
然后分两种情况讨论：
- 若 x 与 2n+1 互质，则有 2t mod (2n+1) = 1
- 若 x 不与 2n+1 互质，设 m = gcd(x, 2n+1)，则有 2t mod m = 1
记第一种情况下的 t 为 t1，第二种情况下记为 t2. 则 t1 必为 t2 的倍数。用反证法证明如下：
假设 t1 不是 t2 的倍数，则可设 t1 = k*t2 + a (0 < a < t2)，
由 2t1 mod (2n+1) = 1 可知 2t1 mod m = 1，即 2k*t2+a mod m = 1，又 2t2 mod m = 1，得
2a mod m = 1，而a < t1，与 t2 的最小性矛盾，所以 t1 必为 t2 的倍数。
由上，我们就可以知道，只要某个与 2n+1 互质的数 x 回到原位，整个序列就一定恢复初始状态。又因为 1 与任何数互质，所以只要对 1 进行模拟就能得到结果。
【思考】
对 1 进行模拟，时间复杂度是线性的。有没有更快的方法呢？
根据欧拉定理，我们知道对于同余方程 2t ≡ 1 (mod 2n+1) 必有一解 t = phi(2n+1)，则最终结果必然为 phi(2n+1) 的约数。证明如下（证明过程和上面证明 t1 是 t2 的倍数的过程相似）：
设最终结果为 ans。显然，ans <= phi(2n+1)。
令 x = phi(2n+1)，假设 x = k*ans+b (0<b<ans)，有
2x ≡ 1 (mod 2n+1)，即2k*ans+b ≡ 1 (mod 2n+1)
又 2ans ≡ 1 (mod 2n+1)，
得 2b ≡ 1 (mod 2n+1)，
因为 b<ans，与 ans 的最小性矛盾，故 phi(2n+1) 是 ans 的倍数。
这样做的时间复杂度低于 O(n)。