| | | |
|
Возведение a в степень b по модулю c
Быстрое возведение в степень
Зная a, b, c (целые числа, не превосходят 2 * 109 ) вычислить a в степени b по модулю c (\(a^b mod \ c\))
| № |
Входные данные |
Выходные данные |
| 1 |
2 10 1000 |
24 |
| |
![]()
|
|
Быстрое возведение в степень
Быстрое возведение в степень
Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:
an=(a2)n/2 при четном n,
an=a*an−1 при нечетном n.
Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет O(logn) .
Входные данные: Вводится действительное число a и целое число n.
Выходные данные: Выведите ответ на задачу.
Нельзя использовать стандартное возведение в степень.
| № |
Входные данные |
Выходные данные |
| 1 |
2
7 |
128 |
| 2 |
1.00001
100000
|
2.71827 |
| |
![]()
|