0Pricing
Coding Interview Prep · Урок

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

Вычисляйте степени с помощью pow(a, b, m)

«Быстрое модульное возведение в степень» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Проблема возведения в степень

Часто требуется возвести число в огромную степень, выполняя все вычисления по модулю. Последовательное умножение на один множитель за раз заняло бы слишком много шагов. ⚡

Наивный способ слишком медленный

Цикл, выполняющий умножение b раз, работает за O(b) шагов. При показателе степени около миллиарда он превысит ограничение по времени ещё до завершения.

for _ in range(b): r = r * a % MOD

Возводите в квадрат для ускорения

Хитрость заключается в возведении в квадрат: a в восьмой степени равно ((a в квадрате) в квадрате) в квадрате. Каждое возведение в квадрат удваивает показатель степени, поэтому огромных степеней можно достичь за несколько шагов.

Считайте показатель степени в двоичном виде

Каждый показатель степени представляет собой сумму степеней двойки — это его двоичная форма. Поэтому умножайте только на те степени основания, которым соответствуют установленные биты, пропуская остальные.

# 13 = 1101 -> a^8 * a^4 * a^1

Проверьте младший бит

Используйте b & 1, чтобы проверить младший бит. Если он равен 1, включите текущее основание в накапливаемый результат, а затем переходите дальше.

if b & 1: result = result * base % MOD

Сдвигайте и возводите в квадрат на каждом шаге

После обработки каждого бита возводите основание в квадрат и сдвигайте показатель степени вправо на один разряд. Для любых реалистичных входных данных цикл выполнится всего примерно от 30 до 60 раз.

base = base * base % MOD
b >>= 1

Объединим всё вместе

Начните с результата, равного 1, затем выполняйте цикл, пока показатель степени положителен. Эта идея быстрого возведения в степень также называется двоичным возведением в степень или возведением в степень методом последовательного возведения в квадрат.

result = 1
while b > 0:
    if b & 1: result = result*base%MOD
    base = base*base%MOD
    b >>= 1

Работает за логарифмическое время

Поскольку на каждом шаге показатель степени уменьшается вдвое, сложность равна O(log b). Так миллиард умножений превращается примерно в тридцать, что укладывается практически в любое ограничение.

В Python есть готовая функция pow

Вам редко придётся писать этот цикл самостоятельно: встроенная функция Python pow(a, b, m) выполняет быстрое возведение в степень по модулю со скоростью чистого C-кода.

print(pow(2, 100, MOD))

Почему это скоро пригодится

Быстрое возведение в степень лежит в основе обратного элемента по модулю по теореме Ферма, с которым Вы познакомитесь далее. Освойте этот приём сейчас — и деление по модулю станет простым.

Сначала уменьшите основание

Перед циклом уменьшите основание с помощью base % MOD. Иначе основание, уже превышающее модуль, будет увеличивать каждое последующее возведение в квадрат.

base = a % MOD

Быстрая проверка

Насколько быстро выполняется быстрое возведение в степень по модулю?

Итоги

Теперь Вы умеете возводить числа в огромные степени за O(log b), возводя их в квадрат и считывая биты. В Python достаточно вызвать pow(a, b, m) и двигаться дальше. 🚀

Часто задаваемые вопросы

Урок «Быстрое модульное возведение в степень» бесплатный?

Да — полный текст урока «Быстрое модульное возведение в степень» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Быстрое модульное возведение в степень»?

Вычисляйте степени с помощью pow(a, b, m) Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Быстрое модульное возведение в степень»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Работа по модулю простого числа
  2. Быстрое модульное возведение в степень
  3. Обратный элемент по модулю через теорему Ферма
  4. nCr с предварительно вычисленными факториалами
← Назад к Coding Interview Prep