Разберём недавнюю задачу про меню в грузинском ресторане.
Решить её можно несколькими способами.

1) Первый и самый «лобовой» из них — перебор. Для небольших чисел вполне сработает, в нашей случае он был бы долгим, но опишем его алгоритм.

В этой задаче есть ограничение — у Георгия было меньше 100 лари.
Все подходящие числа, дающие остаток 1 при делении на 3 можно записать как множество:
A = {1, 4, 7, 10, 13, 16, …, 94, 97}.
Те, что дают остаток 6 при делении на 8 можно записать как такое множество
B = {6, 14, 22, 30, 38, 46, …, 86, 94}.
Числа, имеющие остаток 4 при делении на 5:
С = {4, 9, 14, 19, 24, 29, …, 94, 99}.

Дальше нужно найти пересечение этих множеств. И хоть мы и не выписывали все множества целиком, уже видно, что все три содержат число 94. Оно и будет ответом! На самом деле в пересечении может быть несколько чисел, тогда нужно смотреть, какое из них подходит под условия задачи. Нам повезло: 94 — минимальное число, подходящее под эти условия, следующим будет только 214.
Но видно, что если бы мы действительно выписывали все элементы в каждом множестве, получилось бы ну очень не оптимально.

2) Поэтому здесь очень удобно воспользоваться признаками делимости!
Вот, например, отличное решение в комментариях к исходному посту. Оно построено на исключении неподходящих вариантов. В данной задаче мы рекомендуем именно такой способ.

3) Но существует ещё один метод, который позволяет решать похожие задачи для большего числа уравнений, для более громоздких чисел или в общем виде.
Он основан на Китайской теореме об остатках. По её условию у любой системы уравнений, в которых модули сравнения попарно взаимно просты, существует бесконечное количество решений, причем они отличаются на произведение модулей (например, тут они будут отличаться на 3*5*8 = 120). Именно поэтому после 94 следующим подходящим числом будет 94+120 = 214, а потом 334 и так далее.

Теорема достаточно сложна в ручном применении, для её использования нужно ловко жонглировать операциями в модульной арифметике. Зато она позволяет найти все подходящие числа!
Если у вас есть вопросы по этому алгоритму, можете задавать их в комментариях.


Как видите, хачапури — это лучший повод поговорить о чём угодно! 💪