Бінарне піднесення до степеня

Бінарне піднесення до степеня (також відоме як піднесення до степеня через квадрати) — це прийом, який дозволяє обчислити $a^n$ лише за $O(\log n)$ множень (замість $O(n)$ множень, потрібних для наївного підходу).

Воно також має важливі застосування в багатьох задачах, не пов'язаних з арифметикою, оскільки його можна використовувати з будь-якими операціями, що мають властивість асоціативності:

$$(X \cdot Y) \cdot Z = X \cdot (Y \cdot Z)$$

Найочевидніше це стосується множення за модулем, множення матриць та інших задач, які ми обговоримо нижче.

Коли підходить цей алгоритм?

• Чи потрібно обчислити $a^n$ (або застосувати ту саму операцію $n$ разів) за великого $n$, де лінійні $O(n)$ множень не вкладаються в ліміт часу?
• Чи операція, яку ви повторюєте, асоціативна (множення за модулем, множення матриць, композиція перетворень)? (якщо ні → бінарне піднесення незастосовне)
• Якщо це множення матриць для лінійної рекурентності — чи розмір матриці малий, щоб $O(k^3 \log n)$ було прийнятним?

Алгоритм

Піднесення $a$ до степеня $n$ наївно виражається як множення на $a$, виконане $n - 1$ разів: $a^{n} = a \cdot a \cdot \ldots \cdot a$. Однак цей підхід непрактичний для великих $a$ чи $n$.

$a^{b+c} = a^b \cdot a^c$ та $a^{2b} = a^b \cdot a^b = (a^b)^2$.

Ідея бінарного піднесення до степеня в тому, що ми розбиваємо роботу, використовуючи двійкове представлення показника.

Запишемо $n$ у системі числення за основою 2, наприклад:

$$3^{13} = 3^{1101_2} = 3^8 \cdot 3^4 \cdot 3^1$$

Оскільки число $n$ має рівно $\lfloor \log_2 n \rfloor + 1$ цифр у двійковій системі, нам потрібно виконати лише $O(\log n)$ множень, якщо ми знаємо степені $a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log_2 n \rfloor}}$.

Отже, нам потрібно лише знати швидкий спосіб їх обчислити. На щастя, це дуже просто, оскільки кожен елемент послідовності — це просто квадрат попереднього елемента.

$$\begin{align} 3^1 &= 3 \\ 3^2 &= \left(3^1\right)^2 = 3^2 = 9 \\ 3^4 &= \left(3^2\right)^2 = 9^2 = 81 \\ 3^8 &= \left(3^4\right)^2 = 81^2 = 6561 \end{align}$$

Отже, щоб отримати остаточну відповідь для $3^{13}$, нам потрібно перемножити лише три з них (пропускаючи $3^2$, бо відповідний біт у $n$ не встановлений): $3^{13} = 6561 \cdot 81 \cdot 3 = 1594323$

Остаточна складність цього алгоритму — $O(\log n)$: нам треба обчислити $\log n$ степенів $a$, а потім виконати щонайбільше $\log n$ множень, щоб отримати з них остаточну відповідь.

Наступний рекурсивний підхід виражає ту саму ідею:

$$a^n = \begin{cases} 1 &\text{if } n == 0 \\ \left(a^{\frac{n}{2}}\right)^2 &\text{if } n > 0 \text{ and } n \text{ even}\\ \left(a^{\frac{n - 1}{2}}\right)^2 \cdot a &\text{if } n > 0 \text{ and } n \text{ odd}\\ \end{cases}$$

Реалізація

Спочатку рекурсивний підхід, який є прямим перекладом рекурсивної формули:

C++

long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

Python

def binpow(a: int, b: int) -> int:
    if b == 0:
        return 1
    res = binpow(a, b // 2)
    if b % 2:
        return res * res * a
    return res * res

TypeScript

function binpow(a: bigint, b: bigint): bigint {
  if (b === 0n) return 1n;
  const res = binpow(a, b / 2n);
  return b % 2n ? res * res * a : res * res;
}

Go

func binpow(a, b int64) int64 {
	if b == 0 {
		return 1
	}
	res := binpow(a, b/2)
	if b%2 == 1 {
		return res * res * a
	}
	return res * res
}

Другий підхід виконує те саме завдання без рекурсії. Він обчислює всі степені в циклі та перемножує ті з них, які мають відповідний одиничний біт у $n$. Хоча складність обох підходів однакова, цей підхід буде швидшим на практиці, оскільки в нас немає накладних витрат на рекурсивні виклики.

C++

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

Python

def binpow(a: int, b: int) -> int:
    res = 1
    while b > 0:
        if b & 1:
            res *= a
        a *= a
        b >>= 1
    return res

TypeScript

function binpow(a: bigint, b: bigint): bigint {
  let res = 1n;
  while (b > 0n) {
    if (b & 1n) res *= a;
    a *= a;
    b >>= 1n;
  }
  return res;
}

Go

func binpow(a, b int64) int64 {
	var res int64 = 1
	for b > 0 {
		if b&1 == 1 {
			res *= a
		}
		a *= a
		b >>= 1
	}
	return res
}

Застосування

Ефективне обчислення великих степенів за модулем числа

Задача: Обчислити $x^n \bmod m$. Це дуже поширена операція. Наприклад, вона використовується при обчисленні оберненого елемента за модулем.

Розв'язок: Оскільки ми знаємо, що операція взяття за модулем не заважає множенням ($a \cdot b \equiv (a \bmod m) \cdot (b \bmod m) \pmod m$), ми можемо безпосередньо використати той самий код, лише замінивши кожне множення на множення за модулем:

C++

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

Python

def binpow(a: int, b: int, m: int) -> int:
    a %= m
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % m
        a = a * a % m
        b >>= 1
    return res

TypeScript

function binpow(a: bigint, b: bigint, m: bigint): bigint {
  a %= m;
  let res = 1n;
  while (b > 0n) {
    if (b & 1n) res = (res * a) % m;
    a = (a * a) % m;
    b >>= 1n;
  }
  return res;
}

Go

func binpow(a, b, m int64) int64 {
	a %= m
	var res int64 = 1
	for b > 0 {
		if b&1 == 1 {
			res = res * a % m
		}
		a = a * a % m
		b >>= 1
	}
	return res
}

Зауваження: Цей алгоритм можна прискорити для великих $b >> m$. Якщо $m$ — додатне число і $\gcd(x, m) = 1$, то $x^n \equiv x^{n \bmod (m-1)} \pmod{m}$ для простого $m$ і $x^n \equiv x^{n \bmod{\phi(m)}} \pmod{m}$ для складеного $m$. Це безпосередньо випливає з малої теореми Ферма та теореми Ейлера, докладніше див. статтю про обернені елементи за модулем.

Ефективне обчислення чисел Фібоначчі

Задача: Обчислити $n$-те число Фібоначчі $F_n$.

Розв'язок: Докладніше див. статтю про числа Фібоначчі. Ми лише оглянемо алгоритм у загальних рисах. Щоб обчислити наступне число Фібоначчі, потрібні лише два попередні, оскільки $F_n = F_{n-1} + F_{n-2}$. Ми можемо побудувати матрицю $2 \times 2$, яка описує це перетворення: перехід від $F_i$ та $F_{i+1}$ до $F_{i+1}$ та $F_{i+2}$. Наприклад, застосування цього перетворення до пари $F_0$ та $F_1$ змінить її на $F_1$ та $F_2$. Тому ми можемо піднести цю матрицю перетворення до $n$-го степеня, щоб знайти $F_n$ з часовою складністю $O(\log n)$.

Застосування перестановки $k$ разів

Задача: Вам дано послідовність довжини $n$. Застосуйте до неї задану перестановку $k$ разів.

Розв'язок: Просто піднесіть перестановку до $k$-го степеня за допомогою бінарного піднесення до степеня, а потім застосуйте її до послідовності. Це дасть вам часову складність $O(n \log k)$.

vector<int> applyPermutation(vector<int> sequence, vector<int> permutation) {
    vector<int> newSequence(sequence.size());
    for(int i = 0; i < sequence.size(); i++) {
        newSequence[i] = sequence[permutation[i]];
    }
    return newSequence;
}

vector<int> permute(vector<int> sequence, vector<int> permutation, long long k) {
    while (k > 0) {
        if (k & 1) {
            sequence = applyPermutation(sequence, permutation);
        }
        permutation = applyPermutation(permutation, permutation);
        k >>= 1;
    }
    return sequence;
}

Зауваження: Цю задачу можна розв'язати ефективніше за лінійний час, побудувавши граф перестановки і розглянувши кожен цикл окремо. Тоді можна обчислити $k$ за модулем розміру циклу і знайти остаточну позицію для кожного числа, яке є частиною цього циклу.

Швидке застосування набору геометричних операцій до набору точок

Задача: Дано $n$ точок $p_i$, застосуйте $m$ перетворень до кожної з цих точок. Кожне перетворення може бути зсувом, масштабуванням або поворотом навколо заданої осі на заданий кут. Існує також операція «цикл», яка застосовує заданий список перетворень $k$ разів (операції «цикл» можуть бути вкладеними). Ви маєте застосувати всі перетворення швидше, ніж за $O(n \cdot length)$, де $length$ — загальна кількість перетворень, які треба застосувати (після розгортання операцій «цикл»).

Розв'язок: Подивимося, як різні типи перетворень змінюють координати:

• Операція зсуву: додає до кожної з координат свою константу.
• Операція масштабування: множить кожну з координат на свою константу.
• Операція повороту: перетворення складніше (тут ми не вдаватимемося в деталі), але кожну з нових координат усе одно можна подати як лінійну комбінацію старих.

Як бачите, кожне з перетворень можна подати як лінійну операцію над координатами. Таким чином, перетворення можна записати як матрицю $4 \times 4$ вигляду:

$$\begin{pmatrix} a_{11} & a_ {12} & a_ {13} & a_ {14} \\ a_{21} & a_ {22} & a_ {23} & a_ {24} \\ a_{31} & a_ {32} & a_ {33} & a_ {34} \\ a_{41} & a_ {42} & a_ {43} & a_ {44} \end{pmatrix}$$

яка при множенні на вектор зі старими координатами та одиницею дає новий вектор з новими координатами та одиницею:

$$\begin{pmatrix} x & y & z & 1 \end{pmatrix} \cdot \begin{pmatrix} a_{11} & a_ {12} & a_ {13} & a_ {14} \\ a_{21} & a_ {22} & a_ {23} & a_ {24} \\ a_{31} & a_ {32} & a_ {33} & a_ {34} \\ a_{41} & a_ {42} & a_ {43} & a_ {44} \end{pmatrix} = \begin{pmatrix} x' & y' & z' & 1 \end{pmatrix}$$

(Чому ми вводимо фіктивну четверту координату, спитаєте ви? У цьому й полягає краса однорідних координат, які знаходять чудове застосування в комп'ютерній графіці. Без цього було б неможливо реалізувати афінні операції на кшталт операції зсуву як одне множення матриць, оскільки воно вимагає додати константу до координат. Афінне перетворення стає лінійним перетворенням у вищій вимірності!)

Ось кілька прикладів того, як перетворення подаються в матричній формі:

• Операція зсуву: зсунути координату $x$ на $5$, координату $y$ на $7$ і координату $z$ на $9$.

$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 5 & 7 & 9 & 1 \end{pmatrix}$$

• Операція масштабування: масштабувати координату $x$ на $10$, а дві інші — на $5$.

$$\begin{pmatrix} 10 & 0 & 0 & 0 \\ 0 & 5 & 0 & 0 \\ 0 & 0 & 5 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$

• Операція повороту: повернути на $\theta$ градусів навколо осі $x$ за правилом правої руки (проти годинникової стрілки).

$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos \theta & -\sin \theta & 0 \\ 0 & \sin \theta & \cos \theta & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$

Тепер, коли кожне перетворення описане як матриця, послідовність перетворень можна описати як добуток цих матриць, а «цикл» із $k$ повторень можна описати як матрицю, піднесену до степеня $k$ (що можна обчислити за допомогою бінарного піднесення до степеня за $O(\log{k})$). Таким чином, матрицю, яка представляє всі перетворення, можна спочатку обчислити за $O(m \log{k})$, а потім застосувати її до кожної з $n$ точок за $O(n)$, що дає загальну складність $O(n + m \log{k})$.

Кількість шляхів довжини $k$ у графі

Задача: Дано орієнтований незважений граф з $n$ вершин, знайти кількість шляхів довжини $k$ з будь-якої вершини $u$ до будь-якої іншої вершини $v$.

Розв'язок: Ця задача розглядається докладніше в окремій статті. Алгоритм полягає в піднесенні матриці суміжності $M$ графа (матриці, де $m_{ij} = 1$, якщо є ребро з $i$ до $j$, або $0$ в іншому випадку) до $k$-го степеня. Тоді $m_{ij}$ буде кількістю шляхів довжини $k$ з $i$ до $j$. Часова складність цього розв'язку — $O(n^3 \log k)$.

Зауваження: У тій самій статті розглядається ще одна варіація цієї задачі: коли ребра зважені й потрібно знайти шлях мінімальної ваги, що містить рівно $k$ ребер. Як показано в тій статті, ця задача також розв'язується піднесенням матриці суміжності до степеня. Матриця міститиме вагу ребра з $i$ до $j$, або $\infty$, якщо такого ребра немає. Замість звичайної операції множення двох матриць слід використати модифіковану: замість множення обидва значення додаються, а замість підсумовування береться мінімум. Тобто: $result_{ij} = \min\limits_{1\ \leq\ k\ \leq\ n}(a_{ik} + b_{kj})$.

Варіація бінарного піднесення до степеня: множення двох чисел за модулем $m$

Задача: Перемножити два числа $a$ та $b$ за модулем $m$. $a$ і $b$ вміщуються у вбудовані типи даних, але їхній добуток завеликий, щоб уміститися в 64-бітне ціле число. Ідея полягає в тому, щоб обчислити $a \cdot b \pmod m$ без використання довгої арифметики.

Розв'язок: Ми просто застосовуємо описаний вище алгоритм бінарної побудови, лише виконуючи додавання замість множення. Іншими словами, ми «розклали» множення двох чисел на $O (\log m)$ операцій додавання та множення на два (яке, по суті, є додаванням).

$$a \cdot b = \begin{cases} 0 &\text{if }a = 0 \\ 2 \cdot \frac{a}{2} \cdot b &\text{if }a > 0 \text{ and }a \text{ even} \\ 2 \cdot \frac{a-1}{2} \cdot b + b &\text{if }a > 0 \text{ and }a \text{ odd} \end{cases}$$

Зауваження: Цю задачу можна розв'язати іншим способом, використовуючи операції з рухомою комою. Спочатку обчисліть вираз $\frac{a \cdot b}{m}$ за допомогою чисел з рухомою комою і зведіть його до беззнакового цілого $q$. Відніміть $q \cdot m$ від $a \cdot b$ за допомогою беззнакової цілочисельної арифметики і візьміть це за модулем $m$, щоб знайти відповідь. Цей розв'язок виглядає доволі ненадійним, але він дуже швидкий і дуже простий у реалізації. Докладніше див. тут.

Задачі для практики

• UVa 1230 - MODEX
• UVa 374 - Big Mod
• UVa 11029 - Leading and Trailing
• Codeforces - Parking Lot
• leetcode - Count good numbers
• Codechef - Chef and Riffles
• Codeforces - Decoding Genome
• Codeforces - Neural Network Country
• Codeforces - Magic Gems
• SPOJ - The last digit
• SPOJ - Locker
• LA - 3722 Jewel-eating Monsters
• SPOJ - Just add it
• Codeforces - Stairs and Lines

Відеоматеріали