Оптимизации решения «сложных» задач

В этом разделе мы рассмотрим варианты оптимизации решения «сложных» задач — перебор с возвратом и метод ветвей и границ.

Перебор с возвратом

Общая схема рекурсивного перебора с возратом такая:

def Перебор(Ситуация):
    if Ситуация конечная:
        Завершающая обработка
    else:
        for Действие in Множество всех возможных действий:
            Применить Действие к Ситуация
            Перебор(Ситуация)
            откатить Действие назад

В общем случае, алгоритм перебора с возвратом содержит тест, который по данной подзадаче быстро выдаёт один из трёх ответов:

  1. неудача: подзадача не имеет решения;
  2. успех: найдено решение подзадачи;
  3. неопределённость.

Например в задаче о мирных ферзях неудача — новый ферзь бьёт одного из предыдущих, успех — ферзь успешно поставлен на последнюю линию, неопределённость — новый ферзь не бьёт ни одного из старых.

Нерекурсивный общий вид алгоритма перебора обычно удобно организовывать при помощи очереди задач:

начать с некоторой задачи P[0]
S = {P[0]} # {очередь активных подзадач}
пока S не пусто:
    выбрать подзадачу P ∈ S и удалить её из S
    разбить P на меньшие подзадачи P[1], P[2], ... ‌, P[k] (или сделать k возможных следующих шагов)
    для каждой P[i]:
        если тест(P[i]) = успех:
            вернуть найденное решение
        если тест(P[i]) = неудача:
            отбросить P[i]
        иначе:
            добавить P[i] в S
сообщить, что решения нет
При удачном подборе и реализации процедур тест, выбрать и разбить перебор с возвратами может быть вполне практичным.

Метод ветвей и границ

Этот метод может быть использован не только для задач поиска, но и для задач оптимизации. Допустим, мы решаем задачу минимизации (для задачи максимизации всё аналогично). Как и раньше, мы рассматриваем частичные решения. Нам необходимо понять, какие из них заведомо не приведут к оптимальному решению, чтобы их отбросить и сэкономить время. Отбросить подзадачу можно, если мы знаем, что на этом пути получится решение, худшее уже найденного в другой ветви. Но откуда мы это можем узнать? Для этого надо использовать нижнюю оценку стоимости решения.
начать с некоторой задачи P[0]
S = {P[0]} # {множество активных подзадач}
пока S не пусто:
    выбрать подзадачу (частичное решение) P ∈ S и удалить её из S
    разбить P на меньшие подзадачи P[1], P[2], ... ‌, P[k]
    для каждой P[i]:
        если P[i] является полным решением:
            обновить текущий_минимум с учётом P[i]
        иначе если нижняя_оценка(P[i]) < текущий_минимум:
            добавить P[i] в S
вернуть текущий_минимум

Упражнения

A: Расстановки ферзей

Известно, что на шахматной доске размером 8×8 можно расставить 8 ферзей не бьющих друг друга, причем сделать это можно 92 способами.

Дано натуральное n⩽12. Определите сколькими способами на доске n×n можно расставить n мирных ферзей.

8
92
IDE

B: Расстановки ферзей - 2

Решите предыдущую задачу при ограничении n⩽10, если расстановки ферзей, которые можно получить друг из друга поворотами и отражениями доски считать за одно.

8
12
IDE

C: Грузоподъемность

Грузоподъемность машины \(M\) килограмм. Есть \(n\) ящиков с грузами, масса \(i\)-го ящика равна \(m_i\). Определите, какую наибольшую массу грузов можно увезти на автомашине.

Программа получает на вход действительное число \(M\), затем количество ящиков \(n\le 20\), затем \(n\) действительных чисел: массы ящиков.

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

10 4 1 3 5 8
9.0
1073.15936137 5 359.840622077 640.476657457 63.7703847126 345.949354785 635.448660233
1064.0876642465998
IDE

D: Грузоподъемность - 2

Решите предыдущую задачу в ограничениях \(n\le 23\). Используйте следующие оптимизации:

  1. Отсортировать массы грузов по убыванию. Перебор начинать с более тяжелых грузов, сначала рассматриваем вариант, когда очередной груз берется.
  2. Делается отсечение, если суммарная масса всех взятых грузов превышает вместимость машины.
  3. Делается отсечение, если суммарная масса всех взятых грузов и всех оставшихся грузов меньше наилучшего уже найденного результата (т.е. если заведомо не удастся улучшить результат).
  4. Для быстрого определения суммарной массы всех оставшихся грузов используется предподсчёт.
IDE

E: Задача коммивояжера

На плоскости даны \(n\) точек. Соедините их замкнутой ломаной линией минимальной длины.

Программа получает на вход число \(n\le10\). Далее идет \(n\) действительных чисел: координаты точек.

Выведите одно действительное число: минимальную длину замкнутой ломаной, проходящей через все эти точки. Ответ выводите с точностью в 15 знаков.

4 0 0 1 0 1 1 2 1
4.82842712474619
IDE

F: Задача коммивояжера - 2

Решите задачу коммивояжера в ограничениях \(n\le11\). Используйте следующую оптимизацию:

Делать отсечение, если суммарная длина текущего маршрута больше или равна наилучшему известному замкнутому маршруту (т.е. заведомо не удастся улучшить результат).

IDE

G: Задача коммивояжера - 3

Решите задачу коммивояжера в ограничениях \(n\le12\). Используйте следующую оптимизацию:

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

IDE

H: Равенство

Дано выражение: \[a_1 ? a_2 ? ... ? a_n = S\]

Посчитайте, сколькими способами в этом выражении можно заменить вопросительные знаки на знаки операций сложения и умножения так, чтобы выполнялось равенство.

Программа получает на вход число n и S. Далее идет n натуральных чисел ai.

Выведите одно число — количество расстановок знаков сложения и умножения, дающих верное равенство.

2 4 2 2
2
IDE

I: Монетки

В Волшебной стране используются монетки достоинством A1, A2,…, AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Сначала вводится число N (1⩽N⩽109), затем —число M (1⩽M⩽15) и далее M попарно различных чисел A1, A2,…, AM (1⩽Ai⩽109).

Выведите сначала K — количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число –1 (минус один).

5 2 1 2
3 2 2 1
7 2 1 2
-1
5 2 3 4
0
IDE

Использование эвристик для оптимизации перебора

Если уж дело дошло до полного перебора, то использование эвристик позволяет ускорить его в некоторых случаях на порядки. Представим себе, что мы можем численно оценить «перспективность» конкретного хода или даже всей позиции целиком. В этом случае позиции для следующего шага нужно перебирать в порядке убывания «качества» этого шага или «качества» получаемой позиции. Если есть возможность оценить качество шага, то удобно использовать перебор с возвратом в виде

def Перебор(Ситуация):
    if Ситуация конечная:
        Завершающая обработка
    else:
        for Действие in Множество_всех_возможных_действий,_упорядоченное_по_убыванию_перспективности:
            Применить Действие к Ситуация
            Перебор(Ситуация)
            откатить Действие назад

Если есть возможность оценить «перспективность» позиции целиком, то может оказаться удобно использовать очередь заданий. Соберём все возможные пары (перспективность, задание) в список и отсортируем его. Каждый раз будем удалять из списка самое перспективное задание. Варианты продолжения будем класть назад, поддерживая сортировку (например, используя бинпоиск или bisect.insort, или даже кучу). Итоговый псевдокод получается таким:

задания = [(перспективность_начального_условия, начальное_условие)]
while задания:
    текущее = задания.pop()
    разбить текущее на меньшие подзадачи P[1], P[2], ... ‌, P[k] (или перебрать все возможные продолжения)
    для каждой P[i]:
        если тест(P[i]) = успех:
            вернуть найденное решение
        если тест(P[i]) = неудача:
            отбросить P[i]
        иначе:
            добавить пару (перспективность_P[i], P[i]) в задания
сообщить, что решения нет

Самое сложное — это найти подходящую эвристическую оценку перспективности хода или позиции. Например, в задаче D (Грузоподъёмность — 2) для оценки хода использовалась масса груза: перебор начинался с более тяжёлого. В задаче G (Задача коммивояжера - 3) для оценки хода использовалась расстояние до следующей точки: перебор начинался с ближайшей.
Если мы пытаемся пройти через все вершины в графе, то полезно начинать с вершин, из которой меньше всего выходов.
Если мы пытаемся найти короткий путь в графе, то в качестве оценки позиции можно использовать сумму пройденного пути и эвристической оценки оставшейся части пути.
Если мы пытаемся решить головоломку за минимальное число шагов, то в качестве оценки позиции можно использовать сумму числа уже выполненных ходов и эвристической оценки качества получаемой позиции. При этом для оценки качества позиции можно использовать число шагов для решения задачи по каким-нибудь другим более простым и наглым правилам.

J: Пятнашки

Головоломка «игра в пятнашки» состоит из 15 квадратиков, уложенных в рамку размером 4×4, при этом одно место остается незанятым. За один ход можно передвинуть один квадратик, соседний с незанятым местом, в незанятое место. Цель головоломки: упорядочить квадратики до такого положения:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15

Вам дано некоторое начальное положение головоломки. Известно, что ее можно решить не более, чем за 20 ходов. Найдите решение этой головоломки.

Программа получает на вход 4 строки, содержащие по 4 числа: значения, записанные на квадратиках в начальном расположение. Число 0 соответствует пустой клетке.

Программа должна вывести последовательность перемещений, решающих головоломку в виде строки из букв L, R, U, D решающую головоломку, где буква L соответствует движению квадратика с числом влево, R — вправо, U — вверх, D — вниз.

1 2 3 4 5 6 7 8 9 10 15 11 13 14 0 12
DLU
IDE

K: Пятнашки - 2

В условиях предыдущей задачи найдите и выведите кратчайшее решение (т.е. решение содержащее наименьшее число перемещений). Гарантируется, что головоломку всегда можно решить не более чем за 20 перемещений.

Эвристика
Лучше придумать самому

В качестве оценки позиции можно использовать сумму из числа уже вполненных шагов и количества отличий от уже решённой головоломки.

IDE

L: Кабинет министров

Премьер-министр некоторого государства хочет составить новый кабинет министров. К составу нового кабинета есть следующие пожелания:

  1. Министров должно быть как можно меньше (так ими легче управлять, да и на зарплате можно сэкономить);
  2. Для каждой области государственной деятельности (строительство, финансы, внешняя политика и т.д.) должен быть хотя бы один министр, который в ней разбирается.

На рассмотрение Премьер-министра поступило N кандидатур. Определите, сколько и каких людей должны получить министерские посты, с учетом пожеланий.

Cначала вводится число N (натуральное, не превышает 10) — количество кандидатов в списке, затем вводится число K (натуральное, не превышает 20) – общее количество областей, в которых министры должны разбираться. Затем идет N строк следующего формата: в начале строки вводится число Pi (натуральное, не превышает K) – количество областей, в которых разбирается i-й кандидат, потом вводятся номера этих областей (натуральные числа, не превышают K).

Выведите количество министров, которое планируется назначить, исходя из требований задачи, затем перечислите номера подходящих кандидатов, в порядке возрастания. Если решений несколько, то выберите из них то, в котором участвуют кандидаты, идущие раньше по списку (то есть полученный список должен быть минимальным в лексикографическом порядке из всех возможных списков минимальной длины). Гарантируется, что решение существует (то есть в каждой области разбирается хотя бы один кандидат).

3 2 2 1 2 2 1 2 2 1 2
1 1
4 3 1 1 1 2 1 3 2 1 2
2 3 4
IDE

M: Быстрые шахматы

На шахматной доске (размером 8×8 клеток) расставлены фигуры. За один ход разрешается взять одной фигурой другую (цвет фигур значения не имеет; ходы без взятия делать нельзя). Требуется найти последовательность ходов, после которой на доске останется одна фигура.

Ладья ходит по горизонтали или вертикали на любое число клеток. Слон ходит по диагонали на любое число клеток. Ферзь ходит по горизонтали, вертикали или диагонали на любое число клеток. Эти фигуры не могут перепрыгивать через другие фигуры. Конь ходит на две клетки по горизонтали или вертикали и на одну клетку в перпендикулярном направлении (например, на 2 клетки вверх и на одну клетку вправо и т.п.), при этом он может перепрыгивать через другие фигуры.

В восьми строках входных данных записаны по 8 символов, описывающих шахматную доску: R — ладья, B — слон, K — конь, Q — ферзь, точка обозначает пустую клетку. На доске изначально стоит не менее двух и не более десяти фигур.

Выведите возможную последовательность в следующем формате. Для каждого хода указывается сначала клетка, с которой делается ход, затем двоеточие, затем клетка, на которую делается ход. Клетка задается столбцом и строкой: столбцы нумеруются слева направо строчными латинскими буквами a, b, c, d, e, f, g, h; строки — снизу вверх цифрами 1, 2, 3, 4, 5, 6, 7, 8. Если решений несколько, приведите любое из них. Если решений нет, выведите NO SOLUTION

........ ........ .B...... ........ ........ ....K... ........ ........
b6:e3
K......K ........ .K...... ......Q. ........ ........ ........ K......K
NO SOLUTION
..K..... ..K..... BR...... .B...... ........ ........ ........ ........
c7:a6 b6:a6 b5:a6 a6:c8
IDE

N: Обход доски

Дана шахматная доска размером n×m. Необходимо построить обход всей доски ходом коня так, чтобы конь побывал во всех клетках доски ровно по одному разу. Вы должны сдать на проверку текстовый файл, содержащий код вашей программы, строчку-разделитель ####################, а затем ответ на задачу: nm строчек. Каждая строчка должна содержать координаты ровно одной клетки. Две соседние координаты должны быть связаны ходом коня и каждая из nm клеток доски должна встречаться в этом файле ровно один раз. Каждая клетка записывается в виде «a1», где сначала записывается одна из первых n букв латинского алфавита, затем число от 1 до m. Например, для доски 4×5 сданный файл может быть таким:

код решения #################### a1 c2 d4 b5 a3 b1 d2 c4 a5 b3 c1 a2 b4 d5 c3 d1 b2 a4 c5 d2

Сдайте в тестовую систему файл с путём на доске 20×20. (Ваша программа может работать сколь угодно долго, хоть неделю. Хотя у задачи есть решение на питоне, рвущее задачу для любой доски в пределах 50×50 меньше, чем за секунду)

Эвристика
Лучше придумать самому

Нужно выбирать первыми те клетки, из которых доступно наименьшее количество ещё не посещённых клеток.

IDE

Meet-in-the-middle

Техника оптимизации встреча-посередине в некоторых случаях позволяет поменять память на время. Типичное снижение асимптотики — $O(n^k)\to O(n^{k/2}\cdot \log n \cdot k)$ или $O(2^n) \to O(2^{n/2}\cdot n)$. Метод заключается в том, чтобы разделить задачу пополам, перебрать все варианты и сохранить результат, после чего сопоставить результаты двух половинок.

Meet-in-the-middle имеет смысл применять, если для конкретной задачи выполняются два условия:
1) Время обработки половины данных асимптотически меньше времени получения итогового ответа.
2) Известен асимптотически более быстрый способ получения ответа для всей задачи с использованием информации об обработки её половинок.

Вот пример задачи, в которой эта оптимизация работает очень неплохо: даны $n$ чисел, нужно найти 4 числа, дающие в сумме 0. Тупой перебор потребует $n^4$ шагов. Если числа большие, то динамика нам не поможет. Заметим, что $a+b+c+d=0$ — это то же самое, что $(a+b)=-(c+d)$. Переберём все пары чисел и сохраним сумму в словарь (или просто добавим в список). На это мы потратим $n^2$ времени и столько же памяти. Если мы добавляли значения в список, то отсортируем его (потратив, $n^2 \log (n^2)$). После этого переберём все $n^2$ сумм из словаря/списка. Для каждой суммы $S$ поищем в словаре или в списке бинпоиском сумму $-S$. Если нашли, то вот он наш ответ. В зависимости от реализации итоговая асимптотика будет $n^2$ или $n^2 \log n$.

Другой пример оптимизации meet-in-the-middle может получиться в задаче о рюкзаке. Забравшийся в магазин вор нашёл больше добычи, чем он может унести с собой. Его рюкзак выдерживает не больше $W$ килограммов. Ему надо выбрать какие-то из $n$ товаров веса $w_1, \ldots, w_n$ и стоимости $v_1, \ldots, v_n$. Как найти самый дорогой вариант? Динамическое программирование позволяет решить задачу для целых весов и для малых $W$ за время $O(nW)$. Однако если веса не целые, или число $W$ очень велико, то без перебора не обойтись.
Тупой перебор потребует рассмотреть все подмножества, то есть имеет асимптотику $O(2^n)$ (зато требует $O(n)$ памяти). Подход meet-in-the-middle позволяет улучшить асимптотику до $O(2^{n/2}\cdot n)$ за $O(2^{n/2})$ памяти. Попробуйте придумать эту оптимизацию сами.

Решение

Разделим наше множество на две части. Переберём все подмножества из первой части. Для этого очень удобно использовать алгоритм Эрлиха для перебора всех последовательностей 0 и 1 так, чтобы соседние отличались только в одной позиции (код Грея). Если масса набора не превосходит $W$, то сохраним его в списке. Отсортируем получившийся список (в котором $O(2^{n/2})$ элементов) по весу. Далее пройдемся по этому списку и оставим только те наборы, для которых не существует другого набора с меньшим весом и большей стоимостью. Очевидно, что подмножества, для которых существует другое, более легкое и одновременно более ценное подмножество, можно удалять. Таким образом в нашем списке мы получим наборы, отсортированные не только по весу, но и по стоимости. Теперь начнем перебирать все возможные комбинации вещей из второй половины и находить бинарным поиском удовлетворяющие нам наборы из первой половины.

Заметим также, что подход meet-in-the-middle можно комбинировать с идеей перебора с отсечениями. Для этого мы делим все объекты не совсем поровну. В первой группе мы делаем полный перебор и сохраняем результат. По второй делаем перебор с отсечением (см. задачу D), комбинируя с предпосчитанными и сохранёнными данными.

O: Четыре числа с суммой 0

Дан набор чисел из $n ⩽ 2000$ целых чисел, каждое из которых по модулю не превосходит $10^9$.

Программа должна вывести 4 различных индекса чисел, дающих в сумме 0. Если таких наборов нет, необходимо вывести No solution.

8 -10 -5 -1 0 0 1 5 10
0 3 4 7
8 0 1 2 3 4 5 6 7
No solution
IDE

P: Потерянные транзакции

Имеется список из $n⩽100$ банковских транзакций (каждая сумма не превосходит по модулю $10^{15}$, положительная сумма — зачисление, отрицательная — списание). Из-за сбоя несколько транзакций были неправильно обработаны. Известна полная сумма этих сбойных транзакций. Необходимо все наборы из не более, чем 6 транзакций, с данной суммой.

На вход даются число $n⩽100$ — количество транзакций, число $A$ — сумма сбойных транзакций. В следующей строке даются $n$ целых чисел $a_0, a_1, \ldots, a_{n-1}$, $|a_i|⩽10^{15}$ — суммы транзакций. Необходимо вывести все наборы из не более 6 возрастающих индексов транзакций с данной полной суммой. Порядок наборов неважен.

8 179 179 79 100 -200 21 1000 39 40
2 6 7 1 4 6 7 1 2 0 0 2 3 4 6 7 0 1 2 3 4
IDE

Q: Рюкзак без повторов: наибольший вес

Дано $N$ золотых слитков массой $m_1, \ldots, m_N$. Ими наполняют рюкзак, который выдерживает вес не более $M$. Какую наибольшую массу золота можно унести в таком рюкзаке?

В первой строке вводится натуральное число $N$ ($N ⩽ 40$) и натуральное число $M$ ($M < 10^{15}$). Во второй строке вводятся $N$ натуральных чисел $m_i$, не превышающих $10^{15}$.

Выведите одно целое число — наибольшую возможную массу золота, которую можно унести в данном рюкзаке.

2 3195 38 41
79
IDE

R: Рюкзак без повторов с нецелыми весами с восстановлением ответа

Дано $N$ предметов массой $m_1, \ldots, m_N$ и стоимостью $c_1,\ldots,c_N$ соответственно. Ими наполняют рюкзак, который выдерживает вес не более $M$. Какую наибольшую стоимость могут иметь предметы в рюкзаке?

В первой строке вводится натуральное число $N$, не превышающее 40, и действительное число $M$. Во второй строке вводятся $N$ действительных чисел $m_i$ — массы предметов. В третьей строке вводятся $N$ действительных чисел $c_i$ — стоимости предметов.

В первой строке выведите наибольшую стоимость рюкзака, округлённую до 4-х знаков после запятой. Во второй в порядке возрастания выведите индексы предметов, дающие эту стоимость.

5 17.9 9.6 9.5 0.6 0.8 8.4 7.4 6.7 3.1 6.1 6.1
16.6 0 2 3
IDE

S: ABCDEF

Дан набор $S$ из $n ⩽ 100$ целых чисел. Выведите количество таких шестёрок $(a,b,c,d,e,f)$, что $$ a,b,d,c,e,f\in S; \quad d\ne0;\quad \frac{a\cdot b + c}{d} - e = f $$

1 1
1
2 2 3
4
2 -1 1
24
3 5 7 10
10
IDE

T: Lizard Era: Beginning

В игре Lizard Era: Beginning главному герою предстоит путешествие с тремя спутницами: Линн, Мелианой и Ворриган. Всего в игре $n$ обязательных заданий, для выполнения каждого из них нужно взять ровно двух спутниц.

Отношение каждой из спутниц к герою характеризуется целым числом. Изначально отношение каждой из них к герою нейтрально и равно 0. В процессе выполнения задания главный герой совершает поступки, которые изменяют отношение к нему спутниц, которых он взял на выполнение этого задания, в положительную или отрицательную сторону (а могут и не менять вовсе).

Сообщите, каких спутниц нужно выбирать главному герою, чтобы после выполнения всех заданий значения их отношения к герою были равны между собой. Если это можно сделать несколькими способами, выберите тот, в котором эти значения наибольшие.

Входные данные
В первой строке содержится целое положительное число $n$ ($1 ⩽ n ⩽ 25$) — количество заданий, обязательных для выполнения.

Следующие $n$ строк содержат описание заданий — $i$-я строка содержит три числа li, mi, wi — величины, на которые изменятся отношения к главному герою Линн, Мелианы или Ворриган соответственно, в случае, если герой возьмет их с собой на выполнение $i$-го задания. Все числа во входных данных целые и не превышают по абсолютному значению $10^7$.

Выходные данные
В случае, если решения не существует, в первой строке выведите "Impossible".

В противном случае выведите $n$ строк, в каждой из них по два символа — в $i$-й строке выводите первые буквы имен спутниц, которых герой должен взять с собой на выполнение $i$-ого задания: 'MW', 'LM' или 'LW' ('L' — Линн, 'M' — Мелиана, 'W' — Ворриган). Если решений несколько, выведите любое.

3 1 0 0 0 1 0 0 0 1
LM MW MW
7 0 8 9 5 9 -2 6 -8 -7 9 4 5 -4 -9 9 -4 5 2 -6 8 -7
LM MW LM LW MW LM LW
2 1 0 0 1 1 0
Impossible
IDE

U: Дискретное логарифмирование

Задача дискретного логарифмирования заключается в том, чтобы по данным целым $a$, $b$, $m$ решить уравнение: $$ a^x = b \pmod m,$$ где $a$ и $m$ — взаимно просты. Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны. Полный перебор, очевидно, требует проверить все значения $x$ от 0 до $m-1$, то есть работает за время порядка $O(m)$.

Использование подхода meet-in-the-middle позволяет решить эту задачу за время $O(\sqrt{m})$ или $O(\sqrt{m} \log m)$. Как обычно, идея состоит в том, чтобы ловко выбрать, вычислить и сохранить $\sqrt{m}$ степеней. Затем перебрать ещё $\sqrt{m}$ степеней, выполняя для каждой поиск среди сохранённых значений. При этом должно оказаться, что перебраны все возможные $x$. Для этого уравнение $a^x = b \pmod m$ нужно преобразовать к виду $a^{x+r} = b\cdot a^r \pmod m$, а затем — к виду $a^{s} = b\cdot a^r \pmod m$. Если удастся найти такие $s$ и $r$, что равенство выполнено, то $x=s-r$.

Но какие нужно перебрать $s$ и $r$, чтобы с одной стороны и тех и других было примерно $\sqrt{m}$, а с другой — чтобы это соответствовало перебору всех возможных $x$ от 0 до $m-1$? Для примера возьмём $m=100$. Сначала вычислим $ba^0, ba^1, \ldots, ba^9$ и сохраним в множестве. Дальше вычислим $a^{10}, a^{20}, \ldots, a^{100}$ и тоже сохраним в множестве. Пусть множества пересекаются по элементам $a^{70}=ba^4$. Тогда $x=70-4=66$ — это решение.

Отсюда следует алгоритм. Возьмём $k$, равное $\sqrt{m}$, округлённому вверх. И найдём пересечение множеств $\{b\cdot a^0, b\cdot a^1, \ldots, b\cdot a^k\}$ и $\{a^{1\cdot k}, a^{2\cdot k}, \ldots, a^{k\cdot k}\}$. А из него уже легко найти подходящее $x$.

Выведите такое $0 < x < m$, что $a^x=b \pmod m$. Если такого $x$ не существует, то выведите -1.

3 9 100
2
3 81 100
4
3 67 100
79
3 2 100
-1
IDE
Смотри также:
Задачи на informatics;
Задачи на UVa Online Judge
Задачи на codeforces