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

Задачи из рубрикатора

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

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

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

Входные данные Выходные данные
1 2 10 1000 24

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

Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:
 
an=(a2)n/2 при четном n,
an=a*an−1 при нечетном n.
 
Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет O(logn) .
 
Входные данные: Вводится действительное число a и целое число n.
Выходные данные: Выведите ответ на задачу, с точностью 6 знаков после запятой.
 
Нельзя использовать стандартное возведение в степень.
 
Входные данные Выходные данные 
1 2
7
128
2
1.00001
100000
2.71827