eolymp
bolt
Try our new interface for solving problems
Məsələlər

Абелевы группы

Абелевы группы

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

В стране Берляндии в городе N есть такая традиция. Если девушка хочет выйти замуж за молодого человека, а у него в планах нет дарить ей все возможные ожерелья из шести бусинок, то она должна каждый день дарить ему одну новую абелеву группу порядка N. И только когда все возможные абелевы группы подарены, молодой человек согласится каждый день дарить ей одно новое ожерелье из шести бусинок, и в конце концов они поженятся. При этом если две абелевы группы изоморфны, то они считаются одинаковыми и дарить надо только одну из них. Девушка по имени Афина влюбилась в одного очень занятого программиста по имени Петя. Теперь она хочет узнать сколько дней ей нужно дарить ему абелевы группы, прежде чем он согласится дарить ей ожерелья.

Напомним основные понятия и факты касательно абелевых групп.

Абелева группа это пара G=(A,*), где A - это некоторое множество, а * - это бинарная операция на A, то есть любым двум элементам a и b из A ставится в соответствие элемент a*b, также принадлежащий A. При этом должны быть выполнены следующие свойства, называемые аксиомами абелевой группы:

(i) Ассоциативность: для любых a, b, cA выполнено равенство (a*b)*c=a*(b*c).

(ii) Существует eA такой, что для любого aA выполнены равенства a*e=e*a=a.

(iii) Для любого aA существует bA такой, что выполнены равенства a*b=b*a=e.

(iv) Коммутативность: для любых a, bA выполнено равенство a*b=b*a.

Важным примером абелевой группы является циклическая группа порядка n: множество чисел от 0 до n-1 с операцией сложения по модулю n. Она обозначается как Z_n.

Прямой суммой двух абелевых групп G=(A,*) и H=(B,·) называется пара GH =(C,×), C={(a,b) : aA, bB} и (a_1, b_1)×(a_2, b_2) = (a_1 * a_2, b_1 · b_2) для всех a_1, a_2A и b_1, b_2B.

Две группы G=(A,*) и H=(B,·) называются изоморфными, если существует взаимно однозначное отображение f из A на B такое, что f(a_1)·f(a_2)=f(a_1*a_2) для всех a_1, a_2A.

Фундаментальная теорема теории абелевых групп утверждает, что любая конечная абелева группа изоморфна прямой сумме некоторых циклических групп.

Китайская теорема об остатках утверждает, что Z_mn изоморфно Z_mZ_n тогда и только тогда, когда m и n взаимно просты.

Последние два утверждения позволяют описывать все абелевы группы порядка n с точностью до изоморфизма.

Например, если n - простое, то все группы порядка n изоморфны Z_n.

Существуют 2 неизоморфные группы порядка 4: Z_4 и Z_2Z_2.

Существуют 3 неизоморфные группы порядка 27: Z_27, Z_9Z_3 и Z_3Z_3Z_3.

Существуют 4 неизоморфные группы порядка 36: Z_4Z_9, Z_2Z_2Z_9, Z_4Z_3Z_3 и Z_2Z_2Z_3Z_3.

Giriş verilənləri

В первой строке входного файла задано натуральное число T500, количество тестов. В каждой из последующих T строк задано натуральное число N10^18.

Çıxış verilənləri

Для каждого числа N из входного файла выведите в отдельной строке количество абелевых групп порядка N с точностью до изоморфизма.

Nümunə

Giriş verilənləri #1
4
3
4
27
36
Çıxış verilənləri #1
1
2
3
4