众所周知(?),有限交换群(即有限阿贝尔群)可被分解为若干个质数幂阶循环群的直积。然而沙雕zjt之前一直不知道怎么求出这个分解,最近看了LCA的论文和几篇paper,稍微学习了一个,这里就总结一下吧。

前置知识

有限阿贝尔群基本定理:所有有限阿贝尔群都可以被表示成若干质数幂阶循环子群的直积。(证明naidesu)

Sylow p-子群:现有任意有限群$G$及质数$p$,令$p^k$为能整除$|G|$的最高次幂,则$G$存在阶为$p^k$的子群,称为$G$的Sylow p-子群。在有限交换群中,$G$可以被分解为各个Sylow p-子群的直积。

记$\langle x\rangle$为$x$生成的循环子群,$|\langle x\rangle|$称为$x$的阶,记作$|x|$。以下内容都在某个有限交换群$G$中进行。记$n=|G|$。

线性无关:称$\{b_1,b_2,\cdots,b_k\}$线性无关,当且仅当对于任意$i$,有$\langle b_i\rangle\cap\prod_{j\ne i}\langle b_j\rangle=\{e\}$。若不满足则称为线性相关。元素$x$与集合$A$线性无关的定义类似,即$\{x\}\cup A$线性无关。

基(basis):称$\{b_1,b_2,\cdots,b_k\}$为$G$的一组基,当且仅当$\prod \langle b_i\rangle=G$,且$b_1,b_2,\cdots,b_k$线性无关。

我们要实现的事情是求出$G$的直积分解,并给出对应的基。由于在非交互题中给出整个群就已经是$O(n^2)$的了,这里先介绍一个$O(n^2)$的算法。事实上还存在着复杂度更低甚至线性的算法,这里先咕着(

算法介绍

我们先考虑只有一个Sylow p-子群的情况,即$|G|=p^k$。首先可以$O(n^2)$求出每个元素的阶(这显然不是复杂度下界,不过更低也没啥意义)。算法的基本思路是按照阶从大到小求出每个基,在求的过程中维护与当前基线性相关的元素集合,然后在剩下的集合里选出新的基。

记当前基的集合为$B$,$L$为$B$生成的子群,$M$为所有跟当前基线性相关的元素集合。我们有引理:对于$x\in M,x\notin L$,且$|x|\leq\min_{b\in B}|b|$,一定可以找到$x'\notin M$,使得$\prod_{b\in B\cup{\{x\}}}\langle b\rangle=\prod_{b\in B\cup{\{x'\}}}\langle b\rangle$,且$|x'|\big||x|$。

这个引理说明了,我们贪心在$G\setminus M$中选取阶最大的元素,不会产生$L\ne G$却找不到新的基的情况,即证明了该算法的正确性。

当$G$含有多个Sylow p-子群的情况呢?事实上这个算法依然是对的,因为每个Sylow p-子群内部发生的事情实际上可以看作是独立的,我们每次找出阶最大的元素其实等价于在每个Sylow p-子群内都找出一个阶最大的元素。我们在找出最大阶元素的同时对阶进行一下质因数分解,求出每个Sylow p-子群对应的基即可。

整理一下算法的具体流程:

  1. 求出每个元素的阶
  2. 维护$B,L,M$,初始时$B=\varnothing,L=M=\{e\}$
  3. 在$G\setminus M$中找到阶最大的元素$g$,对$|g|$进行质因数分解,求出每个Sylow p-子群对应的基$g_{p_1},g_{p_2},\cdots$,并加入$B$中
  4. 每当$B$中插入新的基,枚举原有的$L$进行运算,扩展出新的$L$(设新插入的基为$b$,枚举$x\in L,1\leq k<|b|$,将$xb^k$加入$L$中)。每当$L$中有新元素$x$加入,枚举所有$y$使得$y\notin M$且$x$可表示为$y$的幂,把$y$加入$M$中。
  5. 若$L=G$,则找到了所有基,算法结束;否则回到第$3$步

简単でしょう?(本気)

复杂度分析

每一轮扩展$L$的复杂度为$O(|L||b|)$,可以看作是$O(n|b|)$,而所有基的阶之和显然为$O(n)$,所以这一步的复杂度为$O(n^2)$。而每个元素只会被加入$L$中至多一次,所以后面那一步的复杂度也为$O(n^2)$。因此算法的总时间复杂度为$O(n^2)$。

算法实装

ないです。やめたらこの仕事!!

代码的话,等后面更例题的时候再贴吧,应当是会有的(心虚)