Арифметика остатков. Операции по модулю

В этом видео мы разбираем арифметику остатков: как устроены операции по модулю, что такое кольцо вычетов и как правильно брать остаток от деления отрицательных чисел. Рассматриваем алгоритм быстрого возведения в степень, реализуем его рекурсивно и нерекурсивно. Показываем, как деление по модулю сводится к умножению на обратный элемент, и выводим формулу его нахождения через малую теорему Ферма, решаем соответствующие задачи. Тайм-коды: 00:00:00 Начало 00:00:40 Теория остатков. Мотивация 00:09:30 Задача "E. Сумма по модулю" 00:12:30 Арифметика остатков 00:19:20 Свойства остатков 00:25:37 Кольцо вычетов 00:28:00 Цикличность остатков от деления 00:29:35 Остаток от деления отрицательных чисел 00:35:00 Пишем код на C++ к задаче "E. Сумма по модулю" 00:40:45 Быстрое возведение в степень 00:52:22 Рекурсивная реализация на C++ 00:57:55 Нерекурсивная реализация на C++ 01:08:35 Чудеса в C++: 2^1000, точный вывод 01:11:40 Задача "F. A в степени B" 01:18:45 Деление - это умножение на обратный 01:26:00 Нахождение обратного по простому модулю 01:32:28 Малая теорема Ферма 01:39:52 Решение задачи "H. Деление" 01:42:12 Обзор на остальные задачи 01:43:10 Встроенное возведение в степень по модулю в Python3, включая отрицательные степени 01:43:35 Продолжение обзора на остальные задачи 01:47:47 Завершение