Skip to content

11132: 【原1132】群的计数

题目

题目描述

author: Kuan Yang 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1132

Description

群是一种特殊的数学结构,\( (G, \cdot) \)被称为一个群,如果

  • \( G \)是一个集合,群的大小即\( G \)中元素的个数
  • \( \cdot \)是G上的一个二元运算
  • 结合律:\( \forall x, y, z \in G, (x \cdot y) \cdot z = x \cdot (y \cdot z) \)
  • 单位元:\( \exists e \in G, \forall x \in G, e \cdot x = x \cdot e = x \)
  • 逆元:\( \forall x \in G, \exists y \in G, x \cdot y = y \cdot x = e \)

如果群同时还满足交换律,即\( \forall x, y \in G, x \cdot y = y \cdot x \),则它被称为交换群。

Input Format

输入一个数\( n \)

Output Format

输出\( n \)阶交换群的个数(即在同构的意义下,大小为\( n \)的群一共有多少个)

我们称两个群\( (G, \cdot_G) \)和\( (H, \cdot_H) \)同构,如果存在双射\( f: G \rightarrow H \)使得\( \forall x, y \in G, f(x \cdot_G y) = f(x) \cdot_H f(y) \)。

Sample Input 1

2

Sample Output 1

1

Sample Input 2

4

Sample Output 2

2

Sample Input 3

8

Sample Output 3

3

Level

对于\( 50\% \)的数据,\( n \leqslant 100 \),以下\( p, q \)为不同的素数:

  • \( 10\%: n = p \)
  • \( 10\%: n = p^2 \)
  • \( 10\%: n = p^2q \)
  • \( 10\%: n \)的标准分解式中素数的个数不超过2
  • \( 10\%: n \)的标准分解式中素数的最高幂次不超过3

对于另外\( 50\% \)的数据:

  • \( 10\%: 10^2 \leqslant n < 10^3 \)
  • \( 10\%: 10^3 \leqslant n < 10^5 \)
  • \( 10\%: 10^5 \leqslant n < 10^8 \)
  • \( 10\%: 10^8 \leqslant n < 10^{12} \)
  • \( 10\%: 10^{12} \leqslant n < 10^{15} \)

所有数据的答案保证不超过\( 2^{30} \)。

Hint

给出4阶交换群在同构意义下只有两个(即Sample 2)的证明:

对于群中的任意元素\( g \),我们称最小的使得\( g^a = e \)的自然数\( a \)为\( g \)的阶,在有限交换群中,任意元素的阶数是群的大小的因子,所以我们讨论4阶交换群中元素的阶数即可。

若存在某个元素阶数为4,则这个群显然为\( e, g, g^2, g^3 \)

若不存在某个元素阶数为4,则这个群由3个2阶元\( a, b, c \)和单位元\( e \)构成。考虑\( ab \),若\( ab = e \),则\( b=eb=(aa)b=a(ab)=ae=a \),矛盾。若\( ab = a \),则\( b=eb=(aa)b=a(ab)=aa=e \),矛盾,同理\( ab \neq b \)。于是\( ab = ba = c \),同理有\( ac = ca = b, bc = cb = a \),这样在同构的意义下这个群就唯一确定了。

综上4阶交换群只有两个。

请认真看懂以上证明,可以推广出一些结论帮助解决此题。祝你们此题能取得好成绩。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!