pku 2154 Color
   burnside是一種計(jì)數(shù)方法，用來(lái)計(jì)算含有不等價(jià)類的數(shù)量， 簡(jiǎn)單說(shuō)就是對(duì)于每個(gè)置換 fi ，他都對(duì)一定量的著色無(wú)效（該著色經(jīng)過(guò)fi置換不變），設(shè)這些著色數(shù)量為ai，  所有ai的平均數(shù)就是不等價(jià)類的數(shù)量， 當(dāng)然也可以變換求和順序， 先考慮每中著色， 再求他的穩(wěn)定核， 但一般情況是置換數(shù)很少， 著色數(shù)很多， 所以前者很常用
   這道題是比較經(jīng)典的循環(huán)排列計(jì)數(shù)，有 N 個(gè)置換{ P^0 = r, P^1, P^2, P^(n-1)} r為單位置換
   寫(xiě)個(gè)小程序觀察 ，發(fā)現(xiàn) P^x 的循環(huán)結(jié)恰好是gcd（x , N）

   這樣我們就有一個(gè)較好的求和式子 ：
                                      
   但N可到10^9，這個(gè)求和式直接用不現(xiàn)實(shí)，繼續(xù)觀察，發(fā)現(xiàn)這些數(shù)都是N的約數(shù)，自然會(huì)想改變求和順序，先考慮每個(gè)約數(shù)，我又寫(xiě)了個(gè)小程序輸出每個(gè)約數(shù)的數(shù)量（一開(kāi)始就知道他大概跟歐拉數(shù)有關(guān)系，但沒(méi)有發(fā)現(xiàn)明顯的積性），打出表來(lái)一看，原來(lái)因子x的數(shù)量是Phi（N/x）；這樣式子就變成了                   

     φ(N/pi)就是 1 -- N 中所有滿足gcd(i,N)=pi 的 i 的個(gè)數(shù)
                      (Hint gcd（i,N）=pi 等價(jià)于 gcd(i/pi,N/pi)=1 )

   要約數(shù)盡量的多，就要不同的素因子盡量多，N最多不會(huì)有10個(gè)不同的素因子，約數(shù)不會(huì)超過(guò)1024個(gè)，而且約數(shù)越多，約數(shù)就會(huì)變小，求約數(shù)的歐拉數(shù)雖然是O( sqrt(N) )的，但需要對(duì)于其中一個(gè)約數(shù)計(jì)算超過(guò)20次的不會(huì)超過(guò)3個(gè)，有了這些估計(jì)，雖然具體的算法復(fù)雜度不知道， 我決定冒險(xiǎn)試試，應(yīng)該不會(huì)超時(shí)。結(jié)果跑了600ms，還是比較理想的