本文是一個笨比學習組合數學的學習筆記，因為是笨比，所以寫的應該算是很通俗易懂了。

首先，我們考慮這麼一個問題：你有無窮多的\(p\)種顏色的珠子，現在你想要的把他們中的\(n\)個以圓形的形狀等間距的黏在一個可以旋轉的圓盤上，求方案數。

然後，該問題的答案是 \(\frac{1}{n}\Sigma_{d|n}\phi(\frac{n}{d})p^d\) ,之中\(\phi()\)表示歐拉函數，下面解釋一下為什麼會出現這樣一個公式。

首先，我們來複習一下polya定理：設一個序列上定義了一置換群\(|G|\)，則對該序列做\(p\)種顏色的染色，方案數為\(\frac{1}{|G|}\Sigma^{|G|}_{i=1}p^{c_i}\)，之中，\(|G|\)表示置換群大小（元素個數），\(c_i\)表示\(G\)中第\(i\)個置換的循環節數目。

那麼在上述圓排列問題中，置換群也就是旋轉變換的群了，注意這裡不考慮翻轉變換（這也是為什麼題目里說要黏在可旋轉的圓盤上的原因，這樣就和翻轉變換無關了）。那麼顯然，一個有\(n\)個珠子的圓環，一共對應了\(n\)種旋轉變換，分別是從轉\(1\)個單位到轉\(n\)個單位（也就是不轉，或者說轉0個單位）的\(n\)種。因此，置換群大小\(|G|=n\)。

把\(|G|=n\)代入polya的公式里，得到\(ans=\frac{1}{n}\Sigma^{n}_{i=1}p^{c_i}\)，那麼對比真正的答案，接下來要說明的就是，為什麼\(\Sigma^{n}_{i=1}p^{c_i}=\Sigma_{d|n}\phi(\frac{n}{d})p^d\)。

答案其實簡單的有些弱智：合併同類項

\(\Sigma^{n}_{i=1}p^{c_i}\)這一式子里，其實有\(n\)項，那麼很自然的一個想法就是：\(p^{c_i}\)是不是有不少重複的呢？事實上，是的，甚至只有\(\sqrt{n}\)種不同的\(p^{c_i}\)。

下面隨便假設有個指數\(d\)，那我想知道\(\Sigma^{n}_{i=1}p^{c_i}\)，有幾個\(p^d\)出現，也就是有幾個\(c_i=d\)。回憶一下，這裡\(c_i\)指的是第\(i\)個置換循環節的數量，這個要怎麼求呢？這裡需要一個簡單但nb的小知識：

定理：對於\(n\)個珠子組成的圓的旋轉變換來說，旋轉了\(x\)個單位的變換對應的循環節數量有\(gcd(n,x)\)個。

不是證明的證明：考慮一個青蛙跳石頭的問題，也就是有\(n\)塊石頭圓形排列，編號從\(0\)至\(n-1\)，青蛙初始在\(pos\)的位置，每次青蛙會跳x步，那麼青蛙跳一步就相當於\(pos=(pos+x)%k\)，現在，請問青蛙一直跳下去，能踩到多少塊石頭。例如，\(n=6,x=4,pos=2\)時，青蛙就只能跳到編號為\(0,2,4\)的三塊兒石頭上。該問題的答案是\(\frac{n}{gcd(n,x)}\)，這個證明略了，這是個比較好理解但不太好表述的數論結論。

那麼，如果我們把旋轉\(x\)個單位的置換群理解成每步跳\(x\)格的青蛙的話，就有循環節長度 = 青蛙能跳到的石頭個數 = \(\frac{n}{gcd(n,x)}\) 。又因為從青蛙的例子里可以看出，該長度和青蛙初始的\(pos\)無關，所以所有的循環節長度都是\(\frac{n}{gcd(n,x)}\)。
進而，由於 n=循環節長度*循環節數量，就可以解得循環節數量為\(gcd(n,x)\)，這就是旋轉\(x\)對應置換的循環節數量。

書歸正傳，我們現在想知道的是，給定一個整數\(d\)，有幾個\(p^d\)出現在\(\Sigma^{n}_{i=1}p^{c_i}\)中，或者說多少個\(c_i=d\)。\(c_i\)的含義是循環節數量，也就是對於\(x\in [1,n]\)，有多少個\(x\)對應的循環節數量是\(d\)。廢話不多說，按剛才的結論，這也就是問有多少個\(x\)滿足\(gcd(n,x)=d\)。

有多少個\(x\)滿足\(gcd(n,x)=d\)：這又是個數論問題，首先，變換成\(gcd(\frac{n}{d},\frac{x}{d})=1\)，這個變換是科學的，因為\(gcd(n,x)=d\)中\(n\)和\(x\)一定是\(d\)的倍數。那麼，有多少個\(x\)滿足\(gcd(\frac{n}{d},\frac{x}{d})=1\)呢？由於滿足\(gcd(\frac{n}{d},狗)=1\)的狗有\(\phi(n/d)\)個（根據歐拉函數的定義），而狗和\(x\)顯然是一一對應的，所以這樣的\(x\)就也有\(\phi(n/d)\)個。

所以，\(ans=\frac{1}{n}\Sigma^{n}_{i=1}p^{c_i}=\frac{1}{n}\Sigma_{d|n}\phi(\frac{n}{d})p^d\)，這裡\(d|n\)是因為根據上面推導，循環節數量\(d\)顯然一定是\(n\)的因子。