НОД, НОК и быстрое возведение в степень

Два кирпича олимпиадной математики: алгоритм Евклида (НОД за O(log) и быстрое возведение в степень (тоже за O(log)).

НОД (наибольший общий делитель) двух чисел вычисляется алгоритмом Евклида за O(log(min(a, b))); быстрое возведение в степень считает a^n за O(log n) умножений.

Зачем это нужно

Эти два алгоритма — фундамент олимпиадной математики, на котором держится почти весь раздел. НОД нужен для сокращения дробей, для задач на периодичность, на решётки, для НОК. Быстрое возведение в степень незаменимо в модулярной арифметике (вычисление a^n mod p), при работе с большими степенями, в комбинаторике (обратные элементы), при возведении матриц в степень для линейных рекуррент. Оба алгоритма коротки, но идея «логарифмического» подхода в них — образцовая, её стоит прочувствовать.

Алгоритм Евклида для НОД

Идея гениально проста: НОД(a, b) = НОД(b, a mod b), и так пока второе число не станет нулём — тогда первое и есть НОД. Почему работает: любой общий делитель a и b делит и их остаток a mod b, поэтому множество общих делителей не меняется, а числа быстро уменьшаются.

def gcd(a, b):
    while b:
        a, b = b, a % b        # заменяем (a, b) -> (b, остаток)
    return a

def lcm(a, b):
    return a // gcd(a, b) * b   # НОК через НОД (делим раньше умножения)

print("gcd(48, 36) =", gcd(48, 36))
print("gcd(17, 5)  =", gcd(17, 5))
print("lcm(4, 6)   =", lcm(4, 6))
print("lcm(12, 18) =", lcm(12, 18))

НОК выражается через НОД формулой НОК(a, b) = a·b / НОД(a, b). Обрати внимание на порядок: a // gcd(a, b) * b — сначала делим, потом умножаем, чтобы промежуточное произведение не разрослось (в C++ это спасает от переполнения; в Python int бесконечен, но привычка полезна). Алгоритм Евклида делает O(log) шагов — невероятно быстро даже для огромных чисел.

Вывод:

gcd(48, 36) = 12
gcd(17, 5)  = 1
lcm(4, 6)   = 12
lcm(12, 18) = 36

Быстрое (бинарное) возведение в степень

Как посчитать 3^13? Наивно — 13 умножений. Но можно за O(log n)! Идея — разложить показатель по двоичной системе. 13 = 1101₂ = 8 + 4 + 1, поэтому 3^13 = 3^8 · 3^4 · 3^1. А степени 3^1, 3^2, 3^4, 3^8 получаются последовательным возведением в квадрат. Так число умножений падает с n до log₂ n.

def power(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:                    # текущий бит показателя = 1
            result = result * base % mod
        base = base * base % mod       # возводим основание в квадрат
        exp >>= 1                      # сдвигаем показатель вправо
    return result

print("3^13 mod 1000 =", power(3, 13, 1000))
print("2^10 mod 1000 =", power(2, 10, 1000))
print("7^0  mod 1000 =", power(7, 0, 1000))

Разберём механику. Мы идём по битам показателя справа налево. Если текущий бит равен 1 — домножаем result на текущую степень основания. На каждом шаге основание возводится в квадрат (3, 9, 81, ...), а показатель сдвигается вправо (exp >>= 1 делит на 2). За log₂ n итераций показатель обнуляется. Везде берём % mod, чтобы числа не разрастались — это и есть рабочая лошадка модулярной арифметики (следующие уроки).

Вывод:

3^13 mod 1000 = 323
2^10 mod 1000 = 24
7^0  mod 1000 = 1

Где это применяется

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

• Порядок в НОК. Пиши a // gcd * b, а не a * b // gcd — это уменьшает промежуточное значение (важно в языках с фиксированными целыми).
• Готовая функция. В Python есть math.gcd (и math.lcm с 3.9) — на контесте можно брать их; но понимать алгоритм обязательно.
• Граничные случаи. gcd(0, x) = x; степень a^0 = 1 при любом a (наш код это учитывает).
• Не забывай % mod на каждом умножении в быстрой степени — иначе в языках с фиксированными целыми будет переполнение.

Итог

• Алгоритм Евклида: НОД(a, b) = НОД(b, a mod b) за O(log); НОК = a // НОД · b.
• Быстрое возведение в степень считает a^n за O(log n) через двоичное разложение показателя и возведение в квадрат.
• Оба алгоритма — фундамент модулярной арифметики и комбинаторики.
• Бери остаток по модулю на каждом шаге; помни про порядок операций в НОК.