2024-09-29. Делители и факторизация

Все полезные ссылки: Тайм-коды: 00:00:00 Вопросы по задачам с MIREA Welcome Contest 2024 00:02:20 Кто какие языки программирования знает 00:05:15 Кто с какого направления 00:06:12 О задачах и codeforces 00:08:10 Про ICPC и студенческие олимпиады 00:13:00 Об олимпиадных задачах и темах к изучению 00:14:40 Учимся на примере задачи “А. Арбуз“ 00:16:40 Тема: Теория чисел 00:17:30 Факторизация чисел 00:22:08 Поиск всех делителей числа 00:23:55 Различные реализации алгоритма поиска делителей 00:25:30 О скорости работы программы 00:26:55 Вкладка “Запуск“ на codeforces и тест времени работы программы 00:32:10 О тактовой частоте процессора и скорости операций 00:37:50 Сколько действий займёт поиск делителей числа 00:39:55 Экспериментируем и смотрим на делители 00:40:25 Более эффективный алгоритм поиска делителей 00:42:00 Основная идея более быстрого поиска делителей 00:45:00 Оценка количества делителей у чисел 00:46:30 Более точная оценка количества делителей 00:48:30 Алгоритм поиска делителей за O(sqrt(x)) 00:49:40 Убираем из алгоритма ошибки, связанные с sqrt 00:53:30 Об экономии числа операций 00:56:20 Доделываем алгоритм поиска делителей 00:59:00 Фиксим алгоритм для полных квадратов 01:00:30 Обсуждаем задачу k-й делитель 01:07:30 Возрастающий список делителей без сортировки 01:16:30 Фиксим багу в решении k-го делителя 01:23:00 Пишем второе решение: через вектор 01:28:40 Факторизация числа - разложение в произведение простых 01:30:20 Реализация факторизации 01:31:50 Объяснение как это работает 01:36:40 Доделываем особый случай: когда само число простое 01:44:00 Подсказки к домашнему заданию 01:45:15 Подсказки по задаче “B. k-Факторизация“ 01:47:47 Подсказки по задаче “C. n=p^2 x q“ 01:48:50 Подсказки по задаче “D. Удивительное уравнение“ 01:53:23 Подсказки по задаче “E. Максимальный НОД“ 01:55:50 Прощание