eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Факториал, степени и абелевы группы

Факториал, степени и абелевы группы

Лимит времени 4 секунды
Лимит использования памяти 64 MiB

Обозначим через f(n) число абелевых групп порядка n с точностью до изоморфизма. Пусть m и N - фиксированные натуральные числа. Требуется для нескольких пар натуральных чисел L и R таких, что LRN, найти значение суммы

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

Абелева группа это пара 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. Она обозначается как _n.

Прямой суммой двух абелевых групп G=(A,*) и H=(B,·) называется пара GH = (C, ×), где C={(a,b) : a A, b B} и (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.

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

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

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

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

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

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

Существуют 4 неизоморфные группы порядка 36: _4 _9, _2 _2 _9, _4 _3 _3 и _2 _2 _3 _3.

Входные данные

В первой строке входного файла заданы через пробел натуральные числа m10^9, N200000 и T10^5. В каждой из последующих T строк заданы через пробел натуральные числа L, RN такие, что LR.

Выходные данные

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

Пример

Входные данные #1
107 10 3
6 10
3 8
4 6
Выходные данные #1
258
232
130
Автор Антон Лунёв