6624: BZOJ2624：[JSOI2007] 群的计数
Memory Limit：128 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
代数学研究的基本对象之一群是一些元素的集合。这些元素之间有一种代数运算，称之为乘法。两个群元素的乘积是一个群元素。一个大家习以为常的群是有理数乘法群，例如，等等，都是这个群中乘法的例子。需要注意的是，如果仅仅考虑有理数的乘法群，另外的一些运算比如加法是不被讨论的。数学家们把乘法抽象出来，就成为了群。群需要满足以下三条性质： 结合律：对群中的任意元素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) |
| 群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) |
| 群 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) |
输入格式
输入群的阶数n(4<=n<=3000)。
输出格式
输出n阶群的种类数。
样例输入
4
样例输出
2
提示
Hint
注意并灵活运用群的三条性质
题目来源
没有写明来源