Малая теорема Ферма


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 31866. Применение Малой Теоремы Ферма
Темы: Малая теорема Ферма   

Дано число a и простое число p. Найти такое минимальное число x, что \((a * x) \% p = 1\).


Входные данные
На вход подаются два натуральное числа ap (\(a,\ p <= 10^{18} \)).

Выходные данные
Выведите ответ на задачу.
 

 

Примеры
Входные данные Выходные данные
1 2 5 3
 

ID 30699. Банды Фомина №2
Темы: Префиксные суммы(минимумы, ...)    Малая теорема Ферма    Остатки    Быстрое возведение в степень   

Банда Фомина состоит из n групп, в каждой из которых ai человек. Планируется провести q рейдов. В i-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке \([l_i, r_i]\).

Мелехов тоскует, поэтому для каждого рейда он решил посчитать количество возможных отрядов по модулю \(10^9 + 7\). Однако Григорий постоянно находится в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.

Входные данные
В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.
Во второй строке дано n натуральных чисел ai (\(1 <= a_i <= 10^6\)) – количество человек в i-ой группе.
В третьей строке дано число q – количество рейдов.
Далее дано q строк, в каждой из которых дано два числа – li и ri (\(1 <= l_i <= r_i <= n\)) – номера групп, участвующих в i-ом рейде.

Выходные данные
Выведите q чисел, каждое в отдельной строке – ответ на задачу.

 

Примеры
Входные данные Выходные данные
1 6
1 3 7 1 4 100
3
1 3
3 4
2 6
21
7
8400