Group Theory-Burnside-Polya
注意：博客园渲染不等号有点问题，如果你看到一个等号右下方飘着一根杠的话，那玩意其实是不等号，就像这样： \(\neq\)。
群论 / Burnside 引理 / Polya 定理学习笔记。
这是真的边学边记抄，根本记不住，看得昏昏欲睡的。
我现在知道有什么东西是比 062 还抽象的了，抽象代数你抽象死我了。
群以及相关概念
群的定义
群是由一个集合 \(G\) 和一个对 \(G\) 的二元运算 \(\cdot\) 组成的代数结构，记作 \((G, \cdot)\)。
一个群 \((G, \cdot)\) 具有一下性质：
- 封闭性：\(\forall a, b \in G, a \cdot b \in G\)，对于任意两个在集合 \(G\) 中的元素 \(a, b\)，\(a \cdot b\) 也在集合 \(G\) 中。
- 结合律：\((a \cdot b) \cdot c = a \cdot (b \cdot c)\)。
- 单位元（幺元）：\(G\) 中存在一个元素 \(e\) 满足，对于任意一个 \(G\) 中的元素 \(a\) 有 \(a \cdot e = e \cdot a = a\)（若 \(\cdot\) 为乘法 \(\times\)，则 \(e = 1\)，估计这就是名称“幺元”的来由吧。）
- 逆元：对于 \(G\) 中的任意一个元素 \(a\)，\(G\) 中存在一个 \(b\) 使得 \(a \cdot b = b \cdot a = e\)，记为 \(a^{-1}\)。
注意：群不一定满足交换律，满足交换律的群叫交换群（abel 群）。
如果一个代数结构只满足上述性质的前两条（封闭性和结合律），那么称其为“半群”（大概可以理解为满足群的一半性质的东西？），如果还存在单位元，则称为“幺半群”。
例如整数集和整数加法构成的代数结构是一个群 \((\mathbb{Z}, +)\)，封闭性和结合律显然，单位元为 \(0\)，\(a\) 的逆元为 \(-a\)（\(a\) 的相反数）。
（注意从这里开始所有的“乘法”其实都是群的二元运算 \(\cdot\) 了，不是我们平时使用的四则运算的乘法。）
一些衍生的性质：
- 单位元的唯一性：一个群 \((G, \cdot)\) 只存在一个单位元 \(e\)。
反证法：假设存在两个及以上单位元，设其中不同两个分别为 \(e1, e2\)，根据单位元的定义有 \(e1 \cdot e2 = e1 = e2\)，与假设矛盾，故不成立。
- 逆元的唯一性：一个元素 \(a\) 只存在一个逆元 \(a^{-1}\)。
反证法：假设 \(a\) 有两个及以上逆元，设其中不同的两个分别为 \(b, c\)，根据逆元的定义和结合律有 \((b \cdot a) \cdot c = b \cdot (a \cdot c) = e \cdot c = b \cdot e = c = b\)，与假设矛盾，故不成立。
阶
群 \(G\) 的阶是其元素个数，记为 \(\operatorname{ord}(G)\) 或 \(|G|\)。
群 \(G\) 的一个元素 \(a\) 的阶是使得 \(a^{m} = e\) 成立的最小正整数 \(m\)（这里的幂运算和一般的幂运算定义类似，即 \(a^{k} = \underbrace{a \cdot a \cdot a \cdot a \cdots a}_{k \text{ 个 } a}\)）。
无限群有无限阶，无限群的元素不一定有有限阶，有限群的元素一定有有限阶。
子群
若两个群 \((G, \cdot), (H, \cdot)\) 满足 \(H \subseteq G\)，则称 \((H, \cdot)\) 为 \((G, \cdot)\) 的子群。
可以记为 \(H \leqslant G\)。
子群检验法：若群 \(G\) 的非空子集 \(H\) 是子群，其充分必要条件为 \(\forall g, h \in H, g^{-1} \cdot h \in H\)。
必要性显然，证明充分性：
其实本质上是证明其满足封闭性，存在单位元和逆元。
单位元：取 \(h \in H\)，因为 \(h \cdot h^{-1} = e\) 并且 \(h \cdot h^{-1} \in H\)，所以 \(H\) 存在单位元。
逆元：取 \(h \in H\)，因为 \(H\) 存在单位元且 \(h^{-1} \cdot e = h^{-1}\)，所以 \(h^{-1} \in H\)。
封闭性：取 \(g, h \in H\)，因为 \(g\) 有逆元在 \(H\) 中所以 \(g^{-1} \cdot g^{-1} \in H\)，所以 \((g^{-1} \cdot g^{-1})^{-1} \cdot g^{-1} \cdot h = g \cdot g \cdot g^{-1} \cdot h = g \cdot h \in H\)。
注意：关于 \((g^{-1} \cdot g^{-1})^{-1} = g \cdot g\) 如何证明，因为 \(a \cdot b \cdot b^{-1} \cdot a^{-1} = a \cdot a^{-1} = e\)，并且一个元素的逆元唯一，所以 \(a \cdot b\) 的逆元是 \(b^{-1} \cdot a^{-1}\)（不一定是 \(a^{-1} \cdot b^{-1}\)）。
一些特殊的子群（下面两个都用不着，看着玩就行）：
- 生成子群
\(S \subset G\) 的生成子群 \(\langle S \rangle\) 是 \(G\) 的包含 \(S\) 的所有子群中最小的子群，同时也是 \(G\) 的包含 \(S\) 的所有子群的交，称 \(S\) 为群的生成集。
（上面这句话的关系有点复杂，我第一眼愣是没读懂成分。）
若 \(S\) 只有一个元素 \(x\)，则 \(\langle S \rangle\) 通常记为 \(\langle x \rangle\)，同时 \(\langle x \rangle\) 是 \(x\) 的幂的循环子群，称这个循环群是由 \(x\) 生成的。
循环群是指群中的任意一个元素都可以被表示为 \(x^{k}\)，如 \(\langle x \rangle = \left\{x^{k} | k \geqslant 1\right\}\)，称 \(x\) 为其生成元，生成元的阶就是循环群的阶。
- 正规子群
正规子群是在共轭变化下不变的子群。正常地描述就是对于所有的 \(g \in G, h \in H\) 有 \(g^{-1} \cdot h \cdot g \in H\)，那么 \(H\) 是 \(G\) 的正规子群，记为 \(H \triangleleft G\)。
说人话就是：\(H\) 中的每一个元素都和 \(G\) 里的每一个元素满足交换律。
顺便说一下共轭：
如果群中有一个元素 \(g\) 使得 \(b = g^{-1}ag\)，则群的两个元素 \(a\) 和 \(b\) 是共轭的。这是一个等价关系，其等价类称为共轭类。
陪集
其实讲陪集这玩意儿就是用来证明拉格朗日定理的，如果你不感兴趣可以跳过。
拉格朗日定理又是用来证明轨道-稳定子定理的，如果你对证明不感兴趣的话可以直接跳到置换群那里看。
陪集是一个群的子集，简单来说就是将一个群的所有元素都乘上一个相同的元素所得到的集合。
若 \(H\) 是 \(G\) 的一个子群，且有 \(g \in G\)，那么有：
左陪集：\(gH = \left\{g \cdot h | h \in H\right\}\)，称其为 \(H\) 在 \(G\) 中关于 \(g\) 的左陪集。
右陪集：\(Hg = \left\{h \cdot g | h \in H\right\}\)，称其为 \(H\) 在 \(G\) 中关于 \(g\) 的右陪集。
记 \(\left[G : H\right]\) 为 \(G\) 中 \(H\) 的左陪集数（等价于右陪集数）。
关于陪集的一些性质：
- \(|H| = |gH| = |Hg|\)。
根据逆元的唯一性，对于不同的 \(h1, h2\)，\(g \cdot h1 \neq g \cdot h2\)，所以集合大小不变。
容易发现左陪集和右陪集的情况是对称的，所以接下来只讨论右陪集。
- \(\forall g \in G, g \in Hg\)。
根据群的定义可知，\(H\) 中一定含有单位元，所以 \(e \cdot g = g\) 一定在 \(Hg\) 中。
- \(Hg = H \Longleftrightarrow g \in H\)。
后者推前者是显然的，根据群的定义中的封闭性即可证明。
前者推后者也不难，反证即可：\(Hg = H\) 但是 \(H\) 不含 \(g\)，由第二条可知 \(g \in Hg\)，与假设矛盾，故不成立。
- \(Ha = Hb \Longleftrightarrow a \cdot b^{-1} \in H\)。
根据陪集的定义，发现可以在等式两边同时乘上 \(b^{-1}\) 并且仍然相等，所以 \(Hab^{-1} = H\)，根据第三条可知 \(a \cdot b^{-1} \in H\)。
\(Hbb^{-1} = H\) 这一点应该是显然的，根据定义可知 \(Hb = \left\{hb | h \in H\right\}\)，那么 \(Hbb^{-1} = (Hb)b^{-1} = \left\{hbb^{-1} | h \in H\right\} = \left\{h | h \in H\right\} = H\)。
- 对于 \(H\) 在 \(G\) 中的两个陪集 \(Ha, Hb\)，若 \(Ha \neq Hb\)，那么 \(Ha \cap Hb = \varnothing\)。
反证法：假设 \(Ha\) 和 \(Hb\) 不相等且交集不为空，设其中一个元素为 \(c\)，则存在 \(h1, h2 \in H\) 使得 \(h1 \cdot a = h2 \cdot b = c\)，同时左乘一个 \(h1^{-1}\) 右乘一个 \(b^{-1}\)，得到 \(a \cdot b^{-1} = h2 \cdot h1^{-1}\)。
根据群的定义，\(h2 \cdot h1_{-1} \in H\)，所以 \(a \cdot b^{-1} \in H\)，根据第四有 \(Ha = Hb\)，与假设矛盾，故不成立。
- \(H\) 的所有右（左）陪集之并为 \(G\)。
\(H\) 存在单位元，所以 \(\forall g \in G\) 都会出现。
拉格朗日定理
拉格朗日定理：如果 \(H\) 是 \(G\) 的子群，那么 \(|G| = \left[G : H\right]|H|\)。
证明的简要思路是：（左/右）陪集大小等于子群大小（陪集的性质第一条）；而每个陪集要么不相交要么相等（第五条），且所有陪集的并是集合 \(G\)（第六条）；那么陪集数就等于 \(G\) 与 \(H\) 的阶之比。
如果你看懂了上面几条关于陪集的性质那么我相信拉格朗日定理理解起来也不难。
群作用
麻了这么多的知识点好混乱啊懒得整理了。
群作用分为左群作用和右群作用，我们讨论的是左群作用。
对于一个集合 \(S\) 中的任意一个元素 \(a\)，若对于群 \((G, \cdot)\) 中的元素 \(u, v\) 以及它的单位元 \(e\)，有映射 \(G \times S \rightarrow S\)，记作二元运算 \(\circ\)（下面有个置换的乘法也是用的这个符号，不要搞混了），使得：
那么我们称群 \(G\) 作用在集合 \(S\) 上。
其实就是将群的某些性质推广到集合上来。
注意这个群作用的映射 \(\circ\) 是我们自己给定的，这里是真的抽象，要仔细理解，特别是上面那个长得像结合律的东西。
置换群
按理来说置换群应该放在群里面的，为什么要单独拎出来呢？
因为它很特殊/lh
置换
一个有限集合到自身的双射称为一个置换。
简单来说就是把每一个元素替换成集合中的某个元素，要求替换完之后没有元素相同（或者说重新排列一遍？）
例如一个置换：
表示将元素 \(a_{i}\) 映射到 \(a_{p_{i}}\)，\(p_{1 \sim n}\) 是一个 \(1 \sim n\) 的排列。
置换的乘法：
对于两个置换 \(f = \begin{pmatrix}a_{1} & a_{2} & a_{3} & \cdots & a_{n}\\a_{p_{1}} & a_{p_{2}} & a_{p_{3}} & \cdots & a_{p_{n}}\end{pmatrix}, g = \begin{pmatrix}a_{p_{1}} & a_{p_{2}} & a_{p_{3}} & \cdots & a_{p_{n}}\\a_{q_{1}} & a_{q_{2}} & a_{q_{3}} & \cdots & a_{q_{n}}\end{pmatrix}\)，定义置换的乘法 \(g \circ f\) 为：
就是先经过 \(f\) 的映射，再经过 \(g\) 的映射。
置换群
直接搬 OI-wiki 吧。
集合 \(S\) 上的所有置换关于置换的乘法满足封闭性、结合律、有单位元（恒等置换，即每个元素映射成它自己）、有逆元（交换置换表示中的上下两行），因此构成一个群。这个群的任意一个子群即称为置换群。
循环置换
一类特殊的置换可以表示为：
若两个置换不含有相同元素，则称它们是不相交的。
任意一个置换都可以分解为若干个不相交的循环置换的乘积。
证明可以考虑把映射关系建成有向图，容易发现每个点的出度入度都恰好为 \(1\)，所以这个图是由若干个环组成的，一个环恰好可以用一个循环置换表示。
Burnside 引理
学不懂了/kk
今天下午居然没有犯困！看来我每次犯困是真的因为数学的问题了。
轨道-稳定子定理
若有一作用于集合 \(X\) 上的群 \(G\)，那么有以下概念：
- 轨道：对于 \(x \in X\)，称 \(G\) 中所有元素作用于 \(x\) 后的集合，用 \(G(x)\) 表示，即 \(G(x) = \left\{g \circ x | g \in G\right\}\)，我们用 \(g(x)\) 表示群元素 \(g\) 经过 \(x\) 作用后的结果，即 \(g(x) = g \circ x\)。
- 稳定子：对于 \(x \in X\)，\(G\) 中所有经过 \(x\) 作用后等于 \(x\) 的元素形成的集合被称为稳定子，记为 \(G^{x}\)，即 \(G^{x} = \left\{g | g \in G, g(x) = x\right\}\)。（我认为稳定子这个命名非常贴切，挺好记的。）
轨道-稳定子定理：\(|G^{x}| \times |G(x)| = |G|\)
（这里的乘法是我们熟知的四则运算的乘法了，别学群论学魔怔了还在想这玩意是在什么群里的。）
证明思路：先证明 \(G^{x}\) 是 \(G\) 的子群，再运用拉格朗日定理，最后证明 \(|G(x)| = [G : G^{x}]\)
根据稳定子的定义可知 \(G^{x}\) 的元素都是在 \(G\) 中的，那么我们只需要证明 \(G^{x}\) 是一个群即可。
- 封闭性：对于 \(a, b \in G^{x}\)，有 \(a \circ x = b \circ x = x\)，根据群作用的定义有 \(a \circ (b \circ x) = x = (a \cdot b) \circ x\)，根据稳定子的定义有 \(a \cdot b \in G^{x}\)。
- 结合律：显然成立（\(G^{x}\) 的二元运算 \(\cdot\) 就是从群 \(G\) 这里复制过来的）。
- 单位元：根据群作用的定义有 \(e \circ x = x\)，所以 \(e \in G^{x}\)。
- 逆元：若有一元素 \(g \in G^{x}\)，根据群作用的定义有 \((g^{-1} \cdot g) \circ x = e \circ x = x\)，且 \((g^{-1} \cdot g) \circ x = g^{-1} \circ (g \circ x) = g^{-1} \circ x = x\)，所以 \(g^{-1} \in G\)。
我们已经证明了 \(G^{x}\) 是 \(G\) 的一个子群了，运用拉格朗日定理 \(|H| \times [G : H] = |G|(H \leqslant G)\) 后只需要证明 \(|G(x)| = [G : G^{x}]\) 即可。
用文字描述就是：\(G\) 中 \(x\) 的稳定子群的陪集个数等于 \(x\) 的轨道大小。
尝试构建双射关系来证明，令 \(g(x)\) 与 \(gG^{x}\) 建立对应关系。
对于 \(f, g \in G\)，若 \(f(x) = g(x)\)（\(f \circ x = g \circ x\)），所以 \(g^{-1} \circ (f \circ x) = g^{-1} \circ (g \circ x) \Rightarrow (g^{-1} \cdot f) \circ x = e \circ x = x\)，说明 \(g^{-1} \cdot f \in G^{x}\) 且 \((g^{-1} \cdot f)G^{x} = G^{x} \Rightarrow fG^{x} = gG^{x}\)。
若 \(fG^{x} = gG^{x}\) 同样可以反推出 \(f(x) = g(x)\)。我们成功地对任意的 \(g(x)\) 与 \(gG^{x}\) 建立了对应关系，所以 \(|G(x)| = [G : G^{x}]\)，轨道-稳定子定理证明完毕。
Burnside 引理
若有一作用于集合 \(X\) 上的置换群 \(G\)，对于 \(x, y \in X\)，若存在 \(g \in G\) 使得 \(g \circ x = y\)，则定义 \(x, y\) 属于同一个等价类。
用 \(X / G\) 表示 \(X\) 经 \(G\) 作用后的等价类组成的集合（可以理解为按颜色划分称若干块）。
类似上面稳定子的定义，我们用 \(X^{g}\) 表示 \(X\) 中经过 \(g\) 作用后不变的元素组成的集合，即 \(X^{g} = \left\{x | x \in X, g \circ x = x\right\}\)。
关于等价类：对于一个集合 \(S\) 和 \(S\) 上的二元等价关系 \(R\)，这个 \(R\) 需要满足自反（一个元素与自身满足关系），对称（\(a\) 与 \(b\) 满足关系，那么反过来也一定满足），传递性（\(a\) 与 \(b\) 满足关系，\(b\) 与 \(c\) 满足关系，则 \(a\) 与 \(c\) 也满足关系）这三个性质。
那么对于 \(x \in S\)，\(x\) 所属的等价类是所有与 \(x\) 满足关系的元素构成的集合，记为 \([x]_{R} = \left\{y |y \in S, x R y\right\}\)（\(xRy\) 表示元素 \(x\) 和 \(y\) 满足 \(R\) 关系）。
为什么可以按 \(g \circ x = y\) 来划分等价类？证明这东西是个等价关系就好。
- 自反，对于单位元有 \(e \circ x = x\)，成立。
- 对称，假设有 \(g \circ x = y\)，那么有 \(g^{-1} \circ (g \circ x) = g^{-1} \circ y \Rightarrow g^{-1} \circ y = x\)，成立。
- 传递，假设有 \(a \circ x = y, b \circ y = z\)，那么有 \(b \circ (a \circ x) = z \Rightarrow (b \cdot a) \circ x = z\)。
并且证明过后可以发现：同一个等价类中的每一个元素，都可以通过找到合适的群元素 \(g\)，通过对同一个元素 \(x\) 操作来得到。即 \(G(x) = [x]_{R}\)。
Burnside 引理：\(|X / G| = \dfrac{1}{|G|}\sum\limits_{g \in G}|X^{g}|\)。
证明：
右边求和式本质上和对 \(|G^{x}|\) 求和没有区别，因为 \(\sum\limits_{g \in G}|X^{g}| = |\left\{(g, x)|g \in G, x \in X, g \circ x = x\right\}| = \sum\limits_{x \in X}|G^{x}|\)。
开始推柿子：
所以 \(|X / G| = \dfrac{1}{|G|}\sum\limits_{g \in G}|X^{g}|\)。
更加具体且形式化地，给定两个集合 \(A, B\)，\(X\) 代表的是从 \(A\) 到 \(B\) 的一些映射组成的集合，\(G\) 是 \(A\) 上的置换群，并且 \(X\) 中的映射在 \(G\) 的置换作用下封闭。
（注意这里的群作用就是直接拿一个置换来进行置换操作了，所以这里直接称为“置换作用”了。）
Burnside 引理描述的就是在上述条件下关于 \(X / G\) 的公式。
你可能有点难以理解为什么 \(X\) 是 \(A\) 到 \(B\) 的映射，你可以认为 \(B\) 是一个颜色集合，需要解决的问题是将 \(A\) 中元素染色，这样就会好理解很多。下面的 Polya 定理同样可以这么理解。
Polya 定理
（Polya 定理其实应该打成 Pólya 定理的，但是这个 ó 打起来太麻烦了就直接打成 o 了。）
Polya 定理可以理解为特殊情况下的 Burnside 引理，它描述的是：在与 Burnside 引理前提条件相同的情况下，若 \(X\) 是所有从 \(A\) 到 \(B\) 的映射组成的集合，那么有：
其中 \(c(g)\) 表示的是置换 \(g\) 能够拆分成的互不相交的循环置换数量。
需要证明 \(|B|^{c(g)} = |X^{g}|\)。
\(g \circ x = x\) 的充要条件显然是 \(g\) 中的每个循环置换上的元素都映射到了同一元素上（证明考虑依照置换的关系建出有向图，显然会是若干个环组成，若要 \(g \circ x = x\)，那么每个环上需要映射到同一元素），那么映射的方案数就是 \(|X^{g}|\) 了，这个方案数容易根据组合意义得到，即 \(|B|^{c(g)}\)。
至此，我们算是学会了 Burnside 引理和 Polya 定理。
例题
Luogu P4980 【模板】Polya 定理
令 \(A\) 表示环上的元素集合，\(B\) 表示颜色集合，那么对环染色即为建立从 \(A\) 到 \(B\) 的映射，记为 \(X\)。
本质不同的定义是：只需要不能通过旋转与别的染色方案相同。所以令 \(G\) 为循环 \(0 \sim n - 1\) 次的置换构成的置换群，这时 \(|X / G|\) 就是本质不同的染色方案数了，并且满足 Polya 定理的应用条件，直接套 Polya 定理。
答案为：\(\dfrac{1}{n}\sum\limits_{i = 0}^{n - 1}n^{c(p_{i})}\)，其中 \(p_{i}\) 表示循环 \(i\) 次的置换。
如何求 \(c(p_{i})\)？考虑这个置换的本质，相当于每个元素都会被置换到其后面第 \(i\) 个元素，这个描述非常像“步长”，那么对于任意一个元素，它走过了 \(\dfrac{\operatorname{lcm}(i, n)}{i} = \dfrac{n}{\gcd(i, n)}\) 后会回到起点，中途经过的点都是属于同一个循环置换的，所以一个循环置换共有 \(\dfrac{n}{\gcd(i, n)}\) 个元素，那么总共有 \(\gcd(i, n)\) 个循环置换，即 \(c(p_{i}) = \gcd(i, n)\)。
发现 \(\gcd(0, n)\) 不好处理，可以将其视为 \(\gcd(n, n)\)，因为循环 \(n\) 次后的置换不会变。
我们需要求的就是 \(\dfrac{1}{n}\sum\limits_{i = 1}^{n}n^{\gcd(i, n)}\)，枚举公因数，变为 \(\dfrac{1}{n}\sum\limits_{d | n}n^{d}\sum\limits_{i = 1}^{\frac{n}{d}}[\gcd(i, \dfrac{n}{d}) = 1]\)，后面是欧拉函数，直接暴力求即可。
最终答案：\(\dfrac{1}{n}\sum\limits_{d | n}n^{d}\varphi(\dfrac{n}{d})\)。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int mod = 1000000007;
struct modint; modint ksm(modint x, ll y);
struct modint {
int x;
modint(int v = 0): x(v) {}
friend modint operator + (const modint& x, const modint& y) {return x.x + y.x >= mod ? x.x + y.x - mod : x.x + y.x;}
friend modint operator - (const modint& x, const modint& y) {return x.x < y.x ? x.x - y.x + mod : x.x - y.x;}
friend modint operator * (const modint& x, const modint& y) {return (ll)x.x * y.x % mod;}
friend modint operator / (const modint& x, const modint& y) {return x * ksm(y, mod - 2);}
friend modint operator - (const modint& x) {return mod - x.x;}
modint operator ++ (int) {auto ret(x); if((++x) == mod) x = 0; return ret;}
modint& operator ++ () {if((++x) == mod) x = 0; return *this;}
modint operator -- (int) {auto ret(x); if(!(x--)) x = mod - 1; return ret;}
modint& operator -- () {if(!(x--)) x = mod - 1; return *this;}
modint operator = (const modint& _) {x = _.x; return *this;}
modint operator += (const modint& _) {*this = *this + _; return *this;}
modint operator -= (const modint& _) {*this = *this - _; return *this;}
modint operator *= (const modint& _) {*this = *this * _; return *this;}
modint operator /= (const modint& _) {*this = *this / _; return *this;}
bool operator == (const modint& _) const {return x == _.x;}
bool operator != (const modint& _) const {return x != _.x;}
friend istream& operator >> (istream& in, modint& _) {static ll tmp; in >> tmp; _ = tmp; return in;}
friend ostream& operator << (ostream& out, const modint& _) {return out << _.x;}
};
modint ksm(modint x, ll y) {
modint ret = 1;
while(y) {if(y & 1) ret *= x; x *= x, y >>= 1;}
return ret;
}
int t, n;
modint ans;
int phi(int x) {
int ret = x;
for(ll i = 2; i * i <= x; ++i) {
if(!(x % i)) {
ret -= ret / i;
while(!(x % i)) x /= i;
}
}
if(x > 1) ret -= ret / x;
return ret;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> t;
while(t--) {
cin >> n;
ans = 0;
for(ll i = 1; i * i <= n; ++i) {
if(!(n % i)) {
ans += ksm(n, i) * phi(n / i);
if(i != n / i) ans += ksm(n, n / i) * phi(i);
}
}
cout << ans / n << '\n';
}
return 0;
}
UVA 10601 Cubes
恕我空间想象力太差无法颅内模拟正方体的 24 种旋转方式（捂脸）
咱就按照 OI wiki 的描述来讲罢。
- 不动：即恒等变换，因为所有直接染色方案经过恒等变换都不变，有 \(1\) 种。
- 以两个相对面的中心连线为轴的 \(90^\circ\) 旋转：相对面有 \(3\) 种选择，旋转的方向有两种选择，因此这类共有 \(6\) 个置换。
- 以两个相对面的中心连线为轴的 \(180^\circ\) 旋转：相对面有 \(3\) 种选择，旋转方向的选择对置换不再有影响，因此这类共有 \(3\) 个置换。
- 以两条相对棱的中点连线为轴的 \(180^\circ\) 旋转：相对棱有 \(6\) 种选择，旋转方向对置换依然没有影响，因此这类共有 \(6\) 个置换。
- 以两个相对顶点的连线为轴的 \(120^\circ\) 旋转：相对顶点有 \(4\) 种选择，旋转的方向有两种选择，因此这类共有 \(8\) 个置换。
所以总计 \(24\) 种置换。
而这道题的 \(X\) 不是所有的 \(A\) 到 \(B\) 的映射（棱的染色次数有限制，不是任意染色），所以使用 Burnside 引理解决。
现在难点在于计算 \(|X^{g}|\)，即不动点。
上述置换的第 2, 3 种情况可以合并，所以一起考虑。
先不考虑第 4 种情况（因为它的循环置换大小不唯一），剩余情况的循环置换大小都唯一，那么需要先检验是否可以为每个循环置换都染上相同的颜色，即检查每种颜色的染色次数是否都是循环置换的大小的倍数，如果是的话剩下来的就是一个计算可重集排列的问题了，这是容易解决的。
第 4 种情况怎么办呢？发现它特殊的地方在于多了两个大小为 \(1\) 的循环置换，我们直接给这两个循环置换枚举一下它染了什么颜色就好，剩下的部分就按照上述方法计算即可。
代码：
/*
膜拜 Futa
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, x, ans, cnt[10], fct[15];
int calc(int x, int s) {
int ret = fct[s / x];
for(int i = 1; i <= 6; ++i) {
if(cnt[i] % x) return 0;
ret /= fct[cnt[i] / x];
}
return ret;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
fct[0] = 1;
for(int i = 1; i <= 12; ++i) fct[i] = fct[i - 1] * i;
cin >> t;
while(t--) {
fill(cnt + 1, cnt + 7, 0);
for(int i = 1; i <= 12; ++i) {
cin >> x;
++cnt[x];
}
ans = calc(1, 12) + 3 * calc(2, 12) + 8 * calc(3, 12) + 6 * calc(4, 12);
for(int i = 1; i <= 6; ++i) {
if(!cnt[i]) continue;
--cnt[i];
for(int j = 1; j <= 6; ++j) {
if(!cnt[j]) continue;
--cnt[j];
ans += 6 * calc(2, 10);
++cnt[j];
}
++cnt[i];
}
cout << ans / 24 << '\n';
}
return 0;
}