Быстрое возведение в степень


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


Условие задачи Прогресс
ID 31881. Возведение a в степень b по модулю c
Темы: Быстрое возведение в степень   

Зная a, b, c (целые неотрицательные числа, не превосходят \(2\cdot10^9\) ). Вычислите a в степени b по модулю c  (\(a^b mod \ c\)).

Входные данные
На вход подаются три целых неотрицательных числа, разделенных одним пробелом.

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

 

Примеры
№ Входные данные Выходные данные
1 2 10 1000 24

ID 31901. Быстрое возведение в степень
Темы: Быстрое возведение в степень   

Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:

\(a^n=(a^2)^{n/2}\)  при четном n, 
\(a^n=a \cdot a^{n-1}\)  при нечетном n.
 
Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет O(logn) .
 
Входные данные
Вводится вещественное число a и целое число n.
 
Выходные данные 
Выведите ответ на задачу, с точностью 6 знаков после запятой.
 
Нельзя использовать стандартное возведение в степень.
 

 

Примеры
№ Входные данные Выходные данные
1 2
7		 128
2
1.00001
100000
 2.71827

 
ID 39514. Раз-два-три-четыре-пять корову поменять
Темы: Вывод формулы    Быстрое возведение в степень    Перестановки   

N коров (1 ≤ N ≤ 105) Фермера Джона стоят в ряд. i-ая корова слева имеет метку i (1 ≤ i ≤ N).
ФД дал коровам M пар целых чисел s (L1,R1)…(LM,RM), где 1 ≤ M ≤ 100. Затем он сказал коровам повторить ровно K (1 ≤ K ≤ 109) раз процесс из M шагов:

Для каждого i от 1 до M:
Последовательность коров на позициях Li…Ri слева реверсивно меняют свой порядок.
Выведите метки всех коров слева направо для каждого i, (1 ≤ i ≤ N) после завершения описанного процесса.

Входные данные
Первая строка содержит числа N, M, K. Для каждого 1 ≤ i ≤ M строка i+1 содержит Li и Ri, два целых числа в интервале 1…N, где Li<Ri.

Выходные данные
На i-ой строке вывода, выведите i-ый элемент массива после выполнения всех инструкций K раз.

Примеры
№ Входные данные Выходные данные Пояснение
1 
7 2 2
2 5
3 7
 
1
2
4
3
5
7
6
 Изначально порядок коров слева направо такой     [1,2,3,4,5,6,7] 
После первого шага процесса порядок станет таким [1,5,4,3,2,6,7]
После второго шага процесса порядок станет таким [1,5,7,6,2,3,4]. 
Повторив оба шага ещё раз получим результат, приведенный в выводе.

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