Олимпиадное программирование для школьников
Тематический план
Введение в курс
Входное тестирование. Задачи на школьную математику и программирование.
Главное: ты учишься. Ошибки — часть пути. Каждый WA — это шаг к AC!
Целочисленная арифметика
Теория чисел — раздел математики, занимающийся изучением чисел непосредственно как таковых, их свойств и поведения в различных ситуациях. Тема «Целочисленная арифметика» в большей степени уделяет внимание целым числам, их свойствам и алгоритмам работы с ними, которые используются при решении олимпиадных задач.- Задачи на целочисленное деление. Деление с округлением вверх и вниз. Пересечение отрезков. Циклические процессы
⇓ Цифры, последовательности и формулы.
⇓ Делимость и делители. Простые числа и проверка простоты (O sqrt(n)). Решето Эратосфена (O(n log log n))
Пишем функцию проверки числа на простоту с временной эффективностью O(sqrt(n)). Основная теорема арифметики- ⇓ Факторизация (разложение на простые множители) числа O(sqrt(n)*log(n)). Каноническое разложение числа на простые множители: поиск всех делителей числа; нахождение количества делителей числа.
Рассматриваем алгоритм факторизации натуральных чисел с временной сложностью O(sqrt(n)). Пишем функцию канонического разложения на языках программирования Python и C++.