Теория чисел. Делители и факторизация

В этом видео разбираются основные задачи на теорию чисел, которые регулярно встречаются в спортивном программировании. Рассматриваются факторизация числа, количество и сумма делителей, проверка на простоту, разложение на простые множители, поиск всех делителей, а также двоичное представление числа и подсчёт количества единичных битов. Тайм-коды: 00:00:00 Обзор задач по теории чисел 00:02:50 Факторизация числа. Основная теорема арифметики 00:07:00 Количество делителей числа 00:11:00 Общий вид делителей числа через факторизацию 00:14:50 Формула количества делителей числа 00:22:40 Показатель степени заданного простого числа в разложении 00:24:10 Формула суммы делителей числа 00:31:25 Проверка числа на простоту 00:39:40 Алгоритм разложения числа на простые множители 00:49:40 Поиск всех делителей за O(sqrt(n)) 01:12:50 Оценка количества делителей ~ O(cbrt(n)) 01:14:45 Ускоряем разложение на простые множители, изменяя само число n 01:24:00 Поиск любого нечётного делителя, большего 1 01:35:50 Двоичное представление числа 01:37:27 Подсчёт количества единичных битов в числе 01:39:54 Обзор оставшихся задач