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了，可以的话，请您参考添加页面，与大家一起分享你的题解！