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

Быстрое возведение в степень по модулю — операция, без которой не посчитать ни большую степень, ни обратный элемент.

Бинарное возведение в степень вычисляет ab за O(log b) умножений, разбивая показатель на степени двойки.

Зачем это в олимпиадах

Посчитать 21000000 mod (10⁹+7) наивным циклом — миллион умножений, и это ещё терпимо. Но a1018 наивно не взять никогда. Бинарное возведение делает это за ~60 умножений. Эта операция нужна повсюду: обратный элемент по малой теореме Ферма, проверка простоты Миллера–Рабина, возведение матрицы в степень для линейных рекуррент, хеши строк. Это, без преувеличения, самый используемый «строительный блок» олимпиадной алгебры.

Интуиция: удвоение вместо сложения

Чтобы посчитать a13, заметим, что 13 = 1101₂ = 8 + 4 + 1. Значит a13 = a8 · a4 · a1. Степени-двойки a, a2, a4, a8 получаются последовательным возведением в квадрат: каждая следующая — квадрат предыдущей. А какие из них перемножать, подсказывают биты показателя. Идём по битам справа налево: если текущий бит единичный — домножаем результат на текущую степень a; в любом случае возводим a в квадрат и сдвигаем показатель.

Рекуррентно это записывается так: ab равно 1 при b = 0; равно (ab/2)2 при чётном b; равно (a(b−1)/2)2 · a при нечётном. Каждый шаг уменьшает показатель вдвое — отсюда O(log b).

def binpow(a, b):
    result = 1
    while b > 0:
        if b & 1:            # младший бит показателя равен 1
            result *= a
        a *= a              # возводим основание в квадрат
        b >>= 1             # сдвигаем показатель вправо
    return result

print(binpow(2, 13))        # 8192
print(binpow(3, 10))        # 59049
print(2 ** 13, 3 ** 10)     # сверим со встроенной степенью

Вывод:

8192
59049
8192 59049

Версия по модулю

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

MOD = 10**9 + 7

def binpow_mod(a, b, m):
    a %= m                  # на случай a >= m
    result = 1
    while b > 0:
        if b & 1:
            result = result * a % m
        a = a * a % m
        b >>= 1
    return result

print(binpow_mod(2, 100, MOD))
print(pow(2, 100, MOD))                 # встроенная — тот же результат
print(binpow_mod(7, 1_000_000_000, MOD))
print(pow(7, 1_000_000_000, MOD))

Вывод:

976371285
976371285
312556845
312556845

Собственная реализация совпала со встроенной pow — значит логика верна. На олимпиаде по Python используют именно pow(a, b, m): это быстро и без ошибок. Но понимать внутренности обязательно: на C++ такой встроенной функции нет, и вы будете писать binpow руками.

Сложность и почему это так быстро

Цикл выполняется столько раз, сколько битов в b, то есть ⌊log₂ b⌋ + 1. Для b = 1018 это всего около 60 итераций по два умножения каждая — мгновенно. Сравните с наивным циклом из 1018 умножений, который не закончится за время жизни Вселенной. Логарифмическая сложность — то, что превращает невозможное в тривиальное.

Применение: первый взгляд на обратный элемент

Бинарное возведение — мост к делению по модулю. По малой теореме Ферма для простого p и a, не кратного p, выполнено ap−1 ≡ 1 (mod p). Домножив на a−1, получаем a−1 ≡ ap−2 (mod p). То есть обратный элемент — это просто степень, и мы умеем её быстро считать! Подробно — в следующем уроке, а пока проверим идею.

MOD = 10**9 + 7
a = 123456789
inv = pow(a, MOD - 2, MOD)      # обратный по Ферма
print(inv)
print(a * inv % MOD)            # должно быть 1

Вывод:

18633540
1

Разбор задачи: число Фибоначчи по модулю «в лоб» и проверка простоты

Быстрое возведение нужно не только для степеней чисел. Например, тест простоты Ферма использует его напрямую: если p простое, то ap−1 ≡ 1 (mod p) для любого a, не кратного p. Проверив это для нескольких оснований, можно быстро отсеять составные числа (хотя есть редкие числа Кармайкла, обманывающие тест). Покажем вероятностную проверку — она лежит в основе быстрых тестов простоты для огромных чисел, где перебор делителей невозможен.

def fermat_test(n, bases=(2, 3, 5, 7, 11)):
    if n < 2:
        return False
    for a in bases:
        if a % n == 0:
            continue
        if pow(a, n - 1, n) != 1:    # быстрое возведение по модулю
            return False             # точно составное
    return True                      # вероятно простое

print(fermat_test(1_000_000_007))    # большое простое
print(fermat_test(1_000_000_006))    # составное (чётное)
print(fermat_test(561))              # 561 — число Кармайкла, обманывает тест!
# 561 = 3 * 11 * 17, но тест по этим основаниям может ошибиться
print(561 == 3 * 11 * 17)

Вывод:

True
False
False
True

Тест верно распознал большое простое и отсёк чётное составное. Число 561 — знаменитое число Кармайкла: оно составное, но проходит тест Ферма по многим основаниям; здесь основание 3 (делитель 561) его выдало. Главное здесь — pow(a, n-1, n) считается за O(log n) даже для гигантских n, чего наивное возведение не позволило бы. Так быстрое возведение делает возможной проверку простоты больших чисел.

Подводные камни

• Не забывайте a %= m в начале. Если a ≥ m, первое же возведение в квадрат на C++ переполнит тип.
• Показатель ноль. a0 = 1 для любого a (даже формально для 00 в комбинаторных контекстах берут 1) — цикл это обрабатывает: при b = 0 сразу возвращается 1.
• Переполнение в C++. result * a для модуля около 10⁹ требует 64-битного типа. В Python проблемы нет — целые длинные.
• Ферма требует простого модуля и a, не кратного p. Для составного модуля так обратный не находят.

Итог

• Бинарное возведение считает ab за O(log b), используя биты показателя и удвоение основания.
• Версия по модулю берёт % m после каждого умножения; в Python есть готовая pow(a, b, m).
• Логарифмическая сложность делает достижимыми показатели до 1018.
• Обратный элемент по Ферма — это ap−2 mod p, то есть быстрое возведение в степень.