497. Abelian Groups
Time limit per test: 0.25
Memory limit: 262144
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).
, 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
to form another element
. 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
Given two abelian groups G
, their direct sum
is a group where
each element is a pair (g
) with g
operations are performed on each element of the pair independently.
Two groups G
when there exists a one-to-one mapping
from elements of G
to elements of H
such that f
) · f
) = f
) for all a
The fundamental theorem of finite abelian groups
every finite abelian group is isomorphic to a direct sum of several
The Chinese remainder theorem
states that when m
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
First and only line of the input file contains an integer
, 1 ≤ n
In the only line of the output file write the number of abelian groups