- PVSM.RU - https://www.pvsm.ru -

Возведение в степень (задача)

Даны два числа — a и b (Возведение в степень (задача), Возведение в степень (задача), а и b не равны одновременно 0).
Необходимо вывести последнюю цифру десятичной записи числа Возведение в степень (задача).

Решение
Используя факт, что на последнюю цифру произведения влияют только последние цифры перемножаемых чисел, можно реализовать алгоритм быстрого возведения в степень [1], оставляя каждый раз только последнюю цифру (остаток от деления на 10).
Самое лаконичное решение получается на языке Python: встроенная функция pow(a,b,m) имеет третий (необязательный) параметр – модуль, по которому вычисляется результат.
Существует другой способ решения задачи: заметим закономерность, что при возведении числа в степень последняя цифра начинает повторяться с некоторой периодичностью. Например, для двойки: 2,4,8,16,32,64… Возведем все цифры i=0..9 в степень и для каждой определим периодичность t_i последней цифры. Далее, при вводе теста нас интересует только последняя цифра c числа a: найдем остаток от деления b на t_c – это будет номер искомой последней цифры внутри периода.

Автор: ymushnikova

Источник [2]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/zadachi/40499

Ссылки в тексте:

[1] алгоритм быстрого возведения в степень: http://e-maxx.ru/algo/binary_pow

[2] Источник: http://habrahabr.ru/post/189296/