497. Abelian Groups
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard
Andrew has just made a breakthrough in group theory: he realized that he can classify all finite Abelian groups (not much of a breakthrough, indeed). Given
n, how many Abelian groups with
n elements exist up to isomorphism? To help you solve this problem we provide some definitions and theorems from basic algebra (most are cited from Wikipedia). An abelian group is a set,
A, together with an operation '·' that combines any two elements
a and
b to form another element denoted
a ·
b. The symbol '·' is a general placeholder for a concretely given operation. To qualify as an abelian group, the set and operation, (
A, ·), must satisfy five requirements known as the abelian group axioms:
- Closure: for all a, b in A, the result of the operation a · b is also in A.
- Associativity: for all a, b and c in A, the equation (a · b) · c = a · (b · c) holds.
- Identity element: there exists an element e in A, such that for all elements a in A, the equation e · a = a · e = a holds.
- Inverse element: for each a in A, there exists an element b in A such that a · b = b · a = e, where e is the identity element.
- Commutativity: for all a, b in A, a · b = b · a.
An example of an abelian group is a
cyclic group of order
n: the set is integers between 0 and
n-1, and the operation is sum modulo
n. Given two abelian groups
G and
H, their
direct sum is a group where each element is a pair (
g,
h) with
g from
G and
h from
H, and operations are performed on each element of the pair independently. Two groups
G and
H are
isomorphic when there exists a one-to-one mapping
f from elements of
G to elements of
H such that
f(
a) ·
f(
b) =
f(
a ·
b) for all
a and
b. The
fundamental theorem of finite abelian groups states that every finite abelian group is isomorphic to a direct sum of several cyclic groups. The
Chinese remainder theorem states that when
m and
n are coprime, a cyclic group of order
mn is isomorphic to the direct sum of the cyclic group of order
m and the cyclic group of order
n.
Input
First and only line of the input file contains an integer
n, 1 ≤
n ≤ 10
12.
Output
In the only line of the output file write the number of abelian groups with
n elements.
Example(s)
sample input | sample output |
5
|
1
|
sample input | sample output |
4
|
2
|
sample input | sample output |
12
|
2
|