Рекурсия · 12 из 29
Быстрое возведение в степень
Лабораторная «рекурсия», задание из криптографии: 3 в степени 10¹⁸ по модулю 10⁹ + 7. Цикл из 10¹⁸ умножений не кончится до пенсии Бориса Аркадьевича, а само число 3¹⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰ не влезет ни в какую память. Выручает половинка: aⁿ = (a^(n/2))², и на каждом шаге задача становится вдвое меньше. Циклы и pow на этой лабораторной запрещены — только рекурсия.
Что сделать
Возведите a в степень n по модулю m рекурсией через половину степени — без циклов и без pow.
Что приходит
a— основание, целое, не меньше нуляn— показатель, целое, не меньше нуля; бывает огромнымm— модуль, натуральное число
Что вернуть
Остаток от деления a в степени n на m — число от 0 до m − 1.
Допишите функцию stepen в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
Ограничения
Без
pow— и своё имя так назвать нельзяБез цикла
forБез цикла
while
Обходные пути — тоже нарушение: eval, exec, getattr, имена с двойным подчёркиванием, импорт os, subprocess и им подобных.
stepen(3, 13, 7)
3
При n = 0 ответ — 1 % m (при m = 1 это 0).
Иначе: половина p — ответ для степени n // 2; квадрат половины берётся по модулю m; если n нечётное, он домножается ещё на a и снова берётся по модулю.
Глубина рекурсии — около log₂ n: для 10¹⁸ это шестьдесят вызовов.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.