首页 > 代码库 > 洗牌问题

洗牌问题

【问题描述】

设 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

然后分两种情况讨论:

  1. 若 x 与 2n+1 互质,则有 2t mod (2n+1) = 1
  2. 若 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)。

洗牌问题