Обозначение:
\(\mathbb{N}_{0} = \mathbb{N} \cup \{ 0\}\).
\(\left( . \right) \mod m\) – операция взятия остатка от деления по модулю \(m\).

Этот инструмент – модулярная карта степеней – был создан мною для решения проблемы многократного быстрого возведения целых чисел в неотрицательную целую степень по модулю.
Условно говоря, он решает следующую задачу:
Пусть задан некоторый модуль \(m \in \mathbb{N}\), \(m \ge 2\). Даётся \(n \in \mathbb{N}\) следующих запросов:
Даны числа \({\alpha_{i}} \in \mathbb{Z}\) и \(p_{i} \in \mathbb{N}_0\). Для каждой пары этих чисел найти \({\alpha_{i}}^{p_{i}} \mod m\). \(i = \overline{1, n}\).
По сути, если каждый запрос обрабатывать непосредственно считыванием и возведением в степень, асимптотическая сложность решения составит \(O \left( { \sum\limits_{i = 1}^{n} {C \left( p_{i} \right) } } \right)\), где \(C\) – функция сложности возведения произвольного числа в степень \(p_{i}\).

Пусть \(a\) – возводимое в некоторую степень \(n \in \mathbb{N}_{0}\) число. Для наивного алгоритма, который описывается формулой
\(a^n\) \(=\) \(\left\{ \begin{matrix}
1, n=0 \\
a^{n-1} \cdot a, n > 0
\end{matrix}\right.\)
функция сложности имеет вид \(C \left( n \right) = n\).
Для алгоритма бинарного возведения в степень
\(a^n\) \(=\) \(\left\{ \begin{matrix}
1, n=0 \\
a^{n-1} \cdot a, n \mod 2 = 1 \\
{\left(a \cdot a \right)}^{ \frac{n}{2} }, n \mod 2 = 0
\end{matrix} \right.\)
функция сложности имеет вид \(C \left( n \right) = \log_{2}{n}\).
Эти алгоритмы возведения в степень легко модифицируются для возведения в степень по модулю.
Однако, если набор чисел \(p_{i}\) имеет достаточно большую длину \(n\), возведение в степень по модулю может быть довольно громоздкой операцией.

Итак, модулярная карта степеней (далее – МКС) – структура данных, которая позволяет за константное время возводить произвольное число в степень по некоторому модулю \(m\).
Решение данной задачи с помощью модулярной карты степеней вместо асимптотики \(O \left( { \sum\limits_{i = 1}^{n} {C \left( p_{i} \right) } } \right)\) принимает \(O \left( m^{2} + n \right)\), то есть решение задачи перестаёт быть зависимым от самих степеней \(p_{i}\), а сами возведения чисел в степень проводятся мгновенно – за константную сложность.

Решение более общей задачи для возведение чисел в степень \(s \cdot {p_{i}}\), \(s = const \in \mathbb{N}\) (то есть, вместо чисел \({\alpha_{i}}^{p_{i}} \mod m\) из исходной задачи находятся числа \({\left( {\alpha_{i}}^{s} \right)}^{p_{i}} \mod m\)) по модулю \(m\), где \(s \in \mathbb{N}\) – некоторое известное число, проводится с помощью модулярной карты мультистепеней (далее – МКМС). Асимптотика решения также меняется с \(O \left( \sum\limits_{i = 1}^{n} C \left( s \cdot {p_{i}} \right) \right)\) на \(O \left( m^{2} + n \right)\)

Третий вид задач: возведение чисел в повторную степень \(s^{p_{i}}\), \(s = const \in \mathbb{N}\) (то есть, вместо чисел \({\alpha_{i}}^{p_{i}} \mod m\) из исходной задачи находятся числа \({\alpha_{i}}^{\left( s^{p_{i}} \right)} \mod m\)). Данная задача является уже намного более сложной. Возведение в степень одного числа в степень \(s^{p_{i}}\) даже с помощью алгоритма бинарного возведения в степень приобретает линейный характер относительно \(p_{i}\), то есть сложность возведения одного числа в степень \(s^{p_{i}}\) потребует порядка \(O \left( p_{i} \log_{2} s \right)\) операций. Вся же задача в таком случае будет решатся за \(O \left( \sum\limits_{i = 1}^{n} C \left( s^{p_{i}} \right) \right)\), то есть общая сложность может быть весьма ощутимой. Для этого вида задач был разработан третий вид МКС: модулярная карта повторных степеней (далее – МКПС). Решение задачи с её помощью также имеет асимптотику \(O \left( m^{2} + n \right)\).

Идея приведённых структур данных

Исходя из теоретической базы, которая приведена в этой статье делаем вывод, что возведение в степень или умноженную степень (сокращённо – мультистепень) является частично периодичной операцией, и количество вариантов таких степеней является конечным. Поэтому МКС, МКМС и МКПС хранят все варианты чисел и их степеней в рамках этого модуля, по сути, это просто меморизированный результат полного перебора.

При построении МКПС используется МКС, поскольку возведение в повторную степень вместе со знанием предыдущего элемента даст сложность \(O \left( m^2 \log_{2}{s} \right)\), где \(s\) – повторная степень. МКПС строит МКС, и первая использует последнюю для нахождения повторных степеней. Общая сложность построения МКПС при этом составляет \(O \left( m^{2} \right)\)

Код модулярных карт степеней

Другие приложения МКС

Кроме быстрого возведения чисел в степень по модулю, эти структуры данных можно применять для решения степенных сравнений, например, вида:
\(a^{x} \equiv b \left( \mod m \right)\), где \(x \in \mathbb{N}_{0}\) – неизвестная переменная, \(a\), \(b\) \(\in \mathbb{N}_{0}\) – известные коэффициенты, \(m\) – модуль сравнения.
Естественно, это можно делать с помощью полного перебора всех степеней с учётом периода, однако этот полный перебор будет иметь асимптотику \(O \left( m \right)\). Главным преимуществом данного полного перебора будет то, что он будет давать гарантированный результат, а также в качестве ответа можно будет вывести множество всех \(x\), удовлетворяющих данному сравнению.

Инструкция по использованию

1. Скопировать код МКС/МКМС, либо подключить его из независимой библиотеки;
2. Определить некоторый объект типа:
   • МКС modular_powermap, передав конструктору в качестве аргумента некоторый модуль m:
     
     int m; . . . modular_powermap <unsigned int> mpm(m);

     1 2 3

     int m; . . . modular_powermap <unsigned int> mpm(m);

   • МКМС modular_multipowermap, передав конструктору в качестве аргумента некоторый модуль m и множитель степени s:
     
     int m, s; . . . modular_multipowermap <unsigned int> mmpm(m, s);

     1 2 3

     int m, s; . . . modular_multipowermap <unsigned int> mmpm(m, s);

   • МКПС modular_repeatpowermap, передав конструктору в качестве аргумента некоторый модуль m и повторную степень r:
     
     int m, r; . . . modular_repeatpowermap <unsigned int> mrpm(m, r);

     1 2 3

     int m, r; . . . modular_repeatpowermap <unsigned int> mrpm(m, r);

3. Возводить произвольное число num в степень/мультистепень/повторную степень p по модулю m:
   int num; unsigned int p; . . . std::cout << mpm.num_in_power(num, p) << '\n'; std::cout << mmpm.num_in_multipower(num, p) << '\n'; std::cout << mrpm.num_in_repeatpower(num, r) << '\n';

   1 2 3 4 5 6

   int num; unsigned int p; . . . std::cout << mpm.num_in_power(num, p) << '\n'; std::cout << mmpm.num_in_multipower(num, p) << '\n'; std::cout << mrpm.num_in_repeatpower(num, r) << '\n';