杭電acm 1210 Eddy's 洗牌問題

Eddy's 洗牌問題

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 5504    Accepted Submission(s): 3597

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   看到這道題我的，第一感覺是繁瑣，第二感覺是，哈哈，我的大循環可以派上用場了。于是我就模拟了這些數字回家的過程，并記下洗牌次數。可是這種做法是逾時的。acm的題怎麼會那麼簡單，是我大意了。這道題的排列規律其實暗藏玄機，每次把在第x個位置的數移動到位置x*2 mod (2*n+1).而移動p次就是這個式子執行了p次。是以隻要x*2^p mod (2*n+1)等于原數字，p就是所洗牌的次數。

#include<iostream>
using namespace std;
 
int main()
{
    int n,p; 
    while(cin>>n)
    {
        int x=1;
        for(p=1;;p++){
            x=(x*2)%(2*n+1);
            if(x==1)
            break;
        }
        cout<<p<<endl;
    }
}      

轉載于:https://www.cnblogs.com/fromzore/p/9807241.html