Слайд 2Модульная арифметика
Вычисления по модулю:
Сложение: c = (a + b) % MOD;
Вычитание: c
![Модульная арифметика Вычисления по модулю: Сложение: c = (a + b) %](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/958593/slide-1.jpg)
= (a + MOD – b) % MOD
Умножение: с = (a * b) % MOD
Деление (умножение на элемент обратный в кольце по модулю): c = (a * bMOD-2) % MOD
Полезная формула:
Деление с округлением вверх: с = (a + b - 1) / b
Слайд 3Бинарное возведение в степень
Рекурсивная реализация
Вычисление по модулю
![Бинарное возведение в степень Рекурсивная реализация Вычисление по модулю](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/958593/slide-2.jpg)
Слайд 4НОД и НОК
НОД (GCD) – наибольший общий делитель.
Пример: НОД(18, 12) =
![НОД и НОК НОД (GCD) – наибольший общий делитель. Пример: НОД(18, 12)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/958593/slide-3.jpg)
6
НОК (LCM) – наименьшее общее кратное.
Пример: НОК(18, 12) = 36
Слайд 5Алгоритм Евклида
Алгоритм Евклида работает за
O(log min(a, b))
![Алгоритм Евклида Алгоритм Евклида работает за O(log min(a, b))](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/958593/slide-4.jpg)
Слайд 6Простые числа
Простые числа – это натуральные числа, имеющие ровно два различных натуральных
![Простые числа Простые числа – это натуральные числа, имеющие ровно два различных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/958593/slide-5.jpg)
делителя
Например, 2, 3, 5, 7, 11 и т.д.
На олимпиадах часто встречаются задачи, для решения которых нужно определить, является ли заданное число простым.