Eddy's 洗牌問題 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 關於這道題的做法，我這裡復制一下杭電的解題報告： Eddy's洗牌 原始算法： 我們把每個數逛來逛去最後又回家的過程叫做一個循環，循環中經過的位置個數叫做循環的長度。如N=4時，有 兩個循環：1-2-4-8-7-5-1，長度為6；3-6-3，長度為2。答案就是所有循環長度的最小公倍數。顯然算法時空復雜度均為O(n)（因為需要記錄一個數是否已被某個循環經過）。 高效算法： 1所在的循環長度就是答案。時間復雜度小於O(n)，空間復雜度為O(1)，編程復雜度也遠低於原始算法。這個算法是建立在如下結論之上的：“1所在的循環長度是其它任一循環長度的倍數”，或者表述為“1回家時，其它任一數字也一定回了家”。 給出的證明： 題目中的移動規則，其實就是每次把在第x個位置的數移動到位置x*2 mod (2*n+1)。這個式子是十分巧妙的，請用心領悟。由這個式子可以得出任一數字x在p步之後的位置：x*2^p mod (2*n+1)。假設1經過p步回了家，那麼可得1*2^p mod (2*n+1)=1。由此可得對任一數字x，均有x*2^p mod (2*n+1)=x，即1回家時任一數字都回了家。 發代碼： [cpp] #include<iostream> using namespace std; int main() { int num,i,p,sum; while(cin>>num && num!=EOF) { p=2*num+1; for(i=1,sum=1;;i++) { sum=(sum*2)%p; if(sum==1) break; } cout<<i<<endl; } return 0; }
