<br />
<b>Warning</b>:  session_start(): open(/tmp/sess_e6b48bbe67b86b179de3948eecb6d64b, O_RDWR) failed: No space left on device (28) in <b>/data/wiki/inc/init.php</b> on line <b>239</b><br />
<br />
<b>Warning</b>:  session_start(): Failed to read session data: files (path: ) in <b>/data/wiki/inc/init.php</b> on line <b>239</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/auth.php</b> on line <b>430</b><br />
<div class="error">Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed</div><br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
=====莫比乌斯反演推导Burnside引理公式=====

====说在前面====

本文将会用莫比乌斯反演推导$Burnside$引理，其适用于形似于以下的问题：

给出一个长度为$n$的环，需要用$m$种颜色对其进行染色（染色可能有若干限制），请求出有多少本质不同的染色方案，其中我们认为两种染色方案本质相同，当且仅当两种染色方案在旋转后颜色可一一对应（注意此处仅为旋转，不包含翻转）。

====解题过程====

首先我们定义以下函数：

$ans_n$表示环的长度为$n$时的答案。

$f_i$表示长度为$i$的环在不考虑翻转变换的情况下有多少种染色方案。

$g_i$表示长度为$i$且最小循环节为$i$的环在不考虑翻转变换的情况下有多少种染色方案。

根据以上定义，我们可以轻松得出它们之间有以下关系：

$$ans_n=\sum_{i|n}\frac{g_i}{i}=\frac{1}{n}\sum_{i|n}g_i\cdot\frac{n}{i}=\frac{1}{n}(g*id)(n)$$

$$f_i=\sum_{j|i}g_j⇒f=g*1⇒g=f*\mu$$

将第二个式子代入第一个式子可得：

$$ans_n=\frac{1}{n}(f*\mu*id)(n)=\frac{1}{n}(f*\phi)(n)$$

通常情况下由于$f$数组相较于$g$数组限制较少，可以在更快的时间内处理出来，而$\phi$数组可通过线性筛求得。