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

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

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

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