Факториал, степени и абелевы группы
Обозначим через f(n) число абелевых групп порядка n с точностью до изоморфизма. Пусть m и N - фиксированные натуральные числа. Требуется для нескольких пар натуральных чисел L и R таких, что L ≤ R ≤ N, найти значение суммы
Напомним основные понятия и факты касательно абелевых групп.
Абелева группа это пара G=(A,*), где A - это некоторое множество, а * - это бинарная операция на A, то есть любым двум элементам a и b из A ставится в соответствие элемент a*b, также принадлежащий A. При этом должны быть выполнены следующие свойства, называемые аксиомами абелевой группы:
(i) Ассоциативность: для любых a, b, c A выполнено равенство (a*b)*c=a*(b*c).
(ii) Существует e A такой, что для любого a A выполнены равенства a*e=e*a=a.
(iii) Для любого a A существует b A такой, что выполнены равенства a*b=b*a=e.
(iv) Коммутативность: для любых a, b A выполнено равенство a*b=b*a.
Важным примером абелевой группы является циклическая группа порядка n: множество чисел от 0 до n-1 с операцией сложения по модулю n. Она обозначается как _n.
Прямой суммой двух абелевых групп G=(A,*) и H=(B,·) называется пара G H = (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_2 A и b_1, b_2 B.
Две группы G=(A,*) и H=(B,·) называются изоморфными, если существует взаимно однозначное отображение f из A на B такое, что f(a_1)· f(a_2)=f(a_1 * a_2) для всех a_1, a_2 A.
Фундаментальная теорема теории абелевых групп утверждает, что любая конечная абелева группа изоморфна прямой сумме некоторых циклических групп.
Китайская теорема об остатках утверждает, что _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.
Input
В первой строке входного файла заданы через пробел натуральные числа m ≤ 10^9, N ≤ 200000 и T ≤ 10^5. В каждой из последующих T строк заданы через пробел натуральные числа L, R ≤ N такие, что L ≤ R.
Output
Для каждой пары чисел L и R из входного файла выведите в отдельной строке значение соответствующей суммы.