[JSOI2007] 群的计数
时间限制：10s 空间限制：128MB
题目描述
代数学研究的基本对象之一群是一些元素的集合。这些元素之间有一种代数运算，称之为乘法。两个群元素的乘积是一个群元素。一个大家习以为常的群是有理数乘法群，例如，等等，都是这个群中乘法的例子。需要注意的是，如果仅仅考虑有理数的乘法群，另外的一些运算比如加法是不被讨论的。数学家们把乘法抽象出来，就成为了群。群需要满足以下三条性质：
结合律：对群中的任意元素a,b,c 有 a(bc)=(ab)c
单位元：在群中存在唯一的元素e，它对群中任意的元素a有ea=a，ae=a
有理数乘法群的单位元是1
逆 元：对群中任意元素a,都存在群中唯一的元素b,使得ab=ba=e
比如有理数乘法群中，23的逆元就为。从这里可以看出，整数乘法不能构成一个群
需要注意的是，群的定义中并没有交换律，就是说ab不一定等于ba，有理数乘法群作为一个特例，其交换性是没有普遍的意义的
现在的问题是，给定群的元素的个数（群的阶数），需要知道这样的群有多少种。只要满足上述三条性质，就是群，应该算上。
下面用四阶群的例子来说明这个问题。抽象地记群元素为e,a,b,c 只要列出一个乘法表，就可以代表一个群。下面给出推导乘法表的步骤：
|
群1
|
e
|
a
|
b
|
c
|
|
e
|
e (1)
|
a (1)
|
b (1)
|
c (1)
|
|
a
|
a (1)
|
e (2)
|
c (3)
|
b (3)
|
|
b
|
b (1)
|
c (3)
|
e (4)
|
a (5)
|
|
c
|
c (1)
|
b (3)
|
a (5)
|
e (5)
|
有单位元素的性质，可以填上
a*a可能为e,b,c，但不可能为a,否则a*a=a两边乘以a的逆元，得到a=e；
a*a=b和a*a=c的情况是一样的，只是乘法表中元素的位置进行了一个变换，本质没有改变，称为一个群同构；此时可以把a*a得到的元素称为b；
所以只要讨论a*a=e和a*a=b的情况；下面先讨论a*a=e的情况
a*b不能为a或e，a*b为b的话，a=e，也矛盾，所以a*b=c；同理可填上所有的(3)
b*b=e时，b*c=c*b=a，c*c=e，得到群1
b*b=a时，b*c=c*b=e，c*c=a，得到群2
|
群2
|
e
|
a
|
b
|
c
|
|
e
|
e (1)
|
a (1)
|
b (1)
|
c (1)
|
|
a
|
a (1)
|
e (2)
|
c (3)
|
b (3)
|
|
b
|
b (1)
|
c (3)
|
a (4)
|
e (5)
|
|
c
|
c (1)
|
b (3)
|
e (5)
|
a (5)
|
当a*a=b时，按照标号顺序可填出下列的群：
|
群 2’
|
e
|
a
|
b
|
c
|
|
e
|
e (1)
|
a (1)
|
b (1)
|
c (1)
|
|
a
|
a (1)
|
b (2)
|
c (4)
|
e (3)
|
|
b
|
b (1)
|
c (4)
|
e (6)
|
a (5)
|
|
c
|
c (1)
|
e (3)
|
a (5)
|
b (6)
|
但需要注意的是，这并没有得到一个新的群，把群2中的a,b调换位置，就得到了群2’。群2’只是群2的一个同构而已。
综上所述，四阶群一共有2种。
虽然4阶群一定有交换律，但这里再次提醒，这并非一个普遍现象。
输入格式
输入群的阶数n(4<=n<=3000)。
输出格式
输出n阶群的种类数。
样例输入
4
样例输出
2
提示
Hint
注意并灵活运用群的三条性质
题目来源
没有写明来源