Математика для олимпиадного программирования: Фундамент алгоритмов

Теория чисел: алгоритм Евклида, решето Эратосфена и модульная арифметика

Добро пожаловать в курс «Математика для олимпиадного программирования». Если вы занимаетесь спортивным программированием, но чувствуете неуверенность, когда дело доходит до математических задач — вы в правильном месте. Мы не будем углубляться в абстрактные доказательства, которые нужны только профессорам. Наша цель — понять фундамент, на котором строятся эффективные алгоритмы.

Первая статья посвящена «трем китам» базовой теории чисел, которые встречаются в каждой второй задаче уровня Div2/Div3 на соревнованиях: модульной арифметике, поиску НОД (наибольшего общего делителя) и простым числам.

Модульная арифметика: математика на циферблате

В задачах часто просят вывести ответ «по модулю ». Зачем? Потому что ответы могут быть настолько огромными, что не поместятся даже в 64-битный тип данных (long long). Модульная арифметика позволяет нам работать с огромными числами, сохраняя их в пределах разумного диапазона.

Представьте себе обычные часы. Если сейчас 10 часов, то через 5 часов будет не 15, а 3 часа. Это и есть арифметика по модулю 12.

!Аналогия модульной арифметики с часами: переход через границу возвращает к началу

Основная операция

Операция взятия остатка обозначается символом % в коде или в математике.

Где:

— остаток от деления (результат).

— делимое число.

— модуль (делитель).

Например, , так как .

Свойства сложения и умножения

Самое важное правило: мы можем брать остаток на любом этапе вычислений. Это спасает от переполнения типов данных.

Для сложения:

Где:

и — слагаемые.

— модуль.

Для умножения:

Где:

и — множители.

— модуль.

Это значит, что если вам нужно найти , вы можете сначала умножить на , взять остаток, затем умножить на и снова взять остаток.

Коварное вычитание

С вычитанием в программировании есть нюанс. В математике остаток всегда неотрицателен (). Однако в C++ или Java оператор % для отрицательных чисел может вернуть отрицательный результат (например, может вернуть ).

Чтобы избежать ошибок, используйте формулу:

Где:

— уменьшаемое.

— вычитаемое.

— добавление модуля, чтобы гарантировать положительный результат перед финальным взятием остатка.

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

Наибольший общий делитель (НОД, или GCD — Greatest Common Divisor) двух чисел и — это самое большое число, на которое делятся и , и без остатка.

Наивный способ — перебирать все числа от до 1 — работает слишком медленно (). Если числа порядка , программа не уложится в лимит времени.

Древнегреческий математик Евклид придумал гениальный и быстрый способ. Идея основана на факте:

> Если мы заменим большее число на остаток от деления большего на меньшее, НОД не изменится.

Формула алгоритма

Где:

— функция поиска наибольшего общего делителя чисел и .

— остаток от деления на .

!Геометрическая интерпретация алгоритма Евклида: последовательное уменьшение прямоугольника

Пример работы

Найдем НОД(30, 12):

. Теперь ищем НОД(12, 6).

. Теперь ищем НОД(6, 0).

, значит ответ — , то есть 6.

Этот алгоритм работает очень быстро — за логарифмическое время . Даже для чисел с сотней знаков он найдет ответ мгновенно.

НОК (Наименьшее общее кратное)

Зная НОД, легко найти НОК (LCM — Least Common Multiple) — наименьшее число, которое делится и на , и на :

Где:

— наименьшее общее кратное.

— произведение чисел (в коде лучше писать (a / GCD(a, b)) * b, чтобы избежать переполнения при умножении).

Решето Эратосфена: массовый поиск простых чисел

Простое число — это число, которое имеет ровно два делителя: 1 и само себя (2, 3, 5, 7, 11...).

Частая задача: найти все простые числа от 1 до . Если проверять каждое число отдельно, это будет долго. Эратосфен придумал алгоритм «вычеркивания».

Алгоритм

Выпишем все числа от 2 до .

Берем первое невычеркнутое число (это 2) — оно простое.

Вычеркиваем все числа, кратные 2 (4, 6, 8...), кроме самого 2.

Берем следующее невычеркнутое (это 3) — оно простое.

Вычеркиваем все кратные 3 (6, 9, 12...), кроме самого 3.

Повторяем, пока не дойдем до .

!Визуализация процесса вычеркивания чисел в решете Эратосфена

Оптимизация

Начинать вычеркивать кратные числа для числа можно не с , а сразу с . Почему? Потому что меньшие кратные (например, , ) уже были вычеркнуты, когда мы обрабатывали числа 2, 3 и т.д.

Сложность

Сложность этого алгоритма удивительно низкая:

Где:

— верхняя граница диапазона.

— очень медленно растущая функция (для она меньше 5).

Фактически, алгоритм работает почти линейно. Для (10 миллионов) решето Эратосфена отрабатывает меньше чем за секунду на современном компьютере.

Итоги

Сегодня мы заложили фундамент:

Модульная арифметика позволяет работать с гигантскими числами, не вызывая переполнения.

Алгоритм Евклида — золотой стандарт поиска общих делителей.

Решето Эратосфена — лучший способ предварительного расчета простых чисел.

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

Комбинаторика: биномиальные коэффициенты, числа Каталана и принцип включений-исключений

Приветствую вас во второй части курса «Математика для олимпиадного программирования». В прошлой статье мы разобрали теорию чисел, научились искать НОД и работать с остатками. Сегодня мы переходим к одной из самых популярных тем в спортивном программировании — комбинаторике.

Если теория чисел отвечает на вопросы «делится ли?» и «чему равен остаток?», то комбинаторика отвечает на вопрос «сколько способов?». Сколько существует путей в лабиринте? Сколькими способами можно расставить ладьи на доске? Сколько существует правильных скобочных последовательностей?

Мы разберем три фундаментальные концепции, которые помогут решать такие задачи не перебором (который всегда слишком медленный), а элегантными формулами.

Биномиальные коэффициенты: выбор без порядка

Самая базовая задача комбинаторики звучит так: у вас есть разных предметов, и вам нужно выбрать из них штук. Порядок выбора не важен. Сколькими способами это можно сделать?

Это количество обозначается как (читается «це из эн по ка») или . Называется это числом сочетаний.

Формула через факториалы

Математическая формула выглядит так:

Где:

— количество способов выбрать элементов из .

— факториал числа (произведение всех чисел от 1 до ).

— факториал числа (количество перестановок выбранных элементов, на которое мы делим, чтобы исключить учет порядка).

— факториал числа невыбранных элементов.

Пример: Сколькими способами можно выбрать 2 программистов из команды в 5 человек для отправки на олимпиаду?

Где:

.

.

.

Проблема больших чисел и Треугольник Паскаля

Если , то — это число с 158 знаками. Оно не поместится ни в long long, ни в unsigned long long. Как же считать в программировании?

Здесь нам помогает рекуррентное соотношение, известное как правило Паскаля:

Где:

— искомое число сочетаний.

— количество способов, где мы точно взяли конкретный -й элемент.

— количество способов, где мы точно НЕ взяли -й элемент.

Это соотношение лежит в основе Треугольника Паскаля.

!Визуализация построения Треугольника Паскаля: каждое число равно сумме двух верхних соседей.

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

Числа Каталана: магия правильных последовательностей

Иногда в задачах встречается последовательность чисел: 1, 1, 2, 5, 14, 42, 132... Если вы видите эти числа в примерах к задаче (тестовых кейсах), с вероятностью 99% решение связано с числами Каталана.

Числа Каталана () описывают удивительное количество, казалось бы, разных вещей:

Правильные скобочные последовательности: Сколько существует правильных последовательностей из пар скобок? (Например, для : ((())), ()(()), ()()(), (())(), (()()) — всего 5).

Бинарные деревья: Сколько существует различных бинарных деревьев с вершинами?

Триангуляция многоугольника: Сколькими способами можно разбить выпуклый -угольник на треугольники диагоналями, которые не пересекаются?

Формула вычисления

Число Каталана можно выразить через биномиальные коэффициенты:

Где:

— -е число Каталана.

— порядковый номер числа (например, количество пар скобок).

— биномиальный коэффициент (выбор элементов из ).

!Пять возможных бинарных деревьев с 3 вершинами, иллюстрирующие, что 3-е число Каталана равно 5.

Также существует удобная рекуррентная формула, полезная для вычислений:

Где:

— знак суммирования.

— индекс перебора от 0 до .

и — предыдущие числа Каталана.

Эта формула часто используется в динамическом программировании для задач на разбиение структур.

Принцип включений-исключений

Представьте задачу: сколько чисел от 1 до 100 делятся на 2 или на 3?

Если мы просто сложим количество чисел, делящихся на 2 (50 чисел), и количество чисел, делящихся на 3 (33 числа), мы получим 83. Но это неправильно! Почему? Потому что числа, которые делятся и на 2, и на 3 (то есть на 6), мы посчитали дважды (один раз как четные, второй раз как кратные трем).

Чтобы получить верный ответ, нужно вычесть то, что мы посчитали лишний раз.

Формула для двух множеств

Где:

— количество элементов, принадлежащих хотя бы одному из множеств или (объединение).

— количество элементов в множестве .

— количество элементов в множестве .

— количество элементов, принадлежащих обоим множествам одновременно (пересечение).

Для нашего примера:

Чисел, кратных 2: .

Чисел, кратных 3: .

Чисел, кратных 6 (НОК 2 и 3): .

Ответ: .

Общий случай

Что если множеств три? Например, делимость на 2, 3 и 5?

!Диаграмма Венна для трех множеств, показывающая области пересечений.

Правило звучит так:

Складываем размеры всех одиночных множеств.

Вычитаем размеры всех попарных пересечений.

Прибавляем размеры пересечений тройками.

Вычитаем четверками...

И так далее, чередуя знаки и .

Где:

— размеры исходных множеств.

и другие пары — размеры пересечений двух множеств.

— размер пересечения всех трех множеств.

В программировании принцип включений-исключений часто реализуется через битовые маски, перебирая все возможные комбинации множеств и добавляя или вычитая их пересечение в зависимости от количества битов в маске (четное количество — вычитаем, нечетное — прибавляем, или наоборот, в зависимости от формулировки).

Итоги

Сегодня мы добавили в наш арсенал мощные инструменты:

Биномиальные коэффициенты () — позволяют считать количество способов выбрать набор предметов. Мы узнали, что их можно считать через Треугольник Паскаля, чтобы избежать работы с огромными факториалами.

Числа Каталана — универсальная последовательность для задач о правильных структурах (скобки, деревья, многоугольники).

Принцип включений-исключений — метод, позволяющий правильно объединять множества, не считая одни и те же элементы дважды.

Эти темы — база для решения задач уровня Div2 C/D. В следующей статье мы углубимся в теорию графов и узнаем, как алгоритмы обхода помогают находить выходы из лабиринтов и строить связи.