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

Модульная арифметика
Вычисления по модулю:
Сложение: c = (a + b) % MOD;
Вычитание: c = (a + MOD – b) % MOD
Умножение: с = (a * b) % MOD
Деление (умножение на элемент обратный в кольце по модулю): c = (a * bMOD-2) % MOD
Полезная формула:
Деление с округлением вверх: с = (a + b - 1) / b

Бинарное возведение в степень
Рекурсивная реализация
Вычисление по модулю

НОД и НОК
НОД (GCD) – наибольший общий делитель.
Пример: НОД(18, 12) = 6
НОК (LCM) – наименьшее общее кратное.
Пример: НОК(18, 12) = 36

Алгоритм Евклида
Алгоритм Евклида работает за
O(log min(a, b))

Простые числа
Простые числа – это натуральные числа, имеющие ровно два различных натуральных делителя
Например, 2, 3, 5, 7, 11 и т.д.
На олимпиадах часто встречаются задачи, для решения которых нужно определить, является ли заданное число простым.

Наивный метод

Реальный метод

Решето Эратосфена