Задачник Базовый курс EN

Что решает

теория чисел

Статьи

STR Приём Полиномиальный хеш Хеш любого куска строки за O(1) из хешей начал: сравнение подстрок, окна, общие начала — с оценкой вероятности ошибки. O(n) подготовка, O(1) хеш куска 2 задачи DP Приём Динамика по цифрам Счастливые билеты в любом диапазоне за проход по цифрам: 55 252 из миллиона и любой из 10¹⁸ — за миллисекунду. O(D · 10 · S) 2 задачи NUM Алгоритм Алгоритм Евклида Наибольший общий делитель двух чисел за O(log n) делений с остатком. O(log min(a, b)) 2 задачи NUM Алгоритм Быстрое возведение в степень aⁿ за O(log n) умножений: квадраты по битам показателя. O(log n) умножений 2 задачи NUM Алгоритм Решето Эратосфена Все простые до n за O(n log log n): вычёркиваем кратные каждого простого, начиная с его квадрата. O(n log log n) 2 задачи NUM Алгоритм Тест Миллера — Рабина Простота числа за k возведений в степень: основания-свидетели ловят составное, лжецов не больше четверти. O(k log³ n) 2 задачи NUM Алгоритм ρ-алгоритм Полларда Делитель p числа n за ~√p шагов: цикл по модулю неизвестного p, черепаха и заяц, НОД. O(√p) умножений по модулю n 1 задача NUM Алгоритм Китайская теорема об остатках Число по остаткам от нескольких модулей: алгоритм Гарнера и точные вычисления по многим простым. O(k²) операций с машинными числами 2 задачи NUM Алгоритм Теоретико-числовое преобразование БПФ без округлений: корень из единицы — 17 по модулю 3329, и так ваш браузер умножает многочлены постквантового ключа. O(n log n) 1 задача NUM Алгоритм Генераторы псевдослучайных чисел Откуда берутся «случайные» числа, почему плохой генератор видно по плоскостям и как его проверить. O(1) на число 2 задачи GEO Алгоритм Площадь многоугольника Площадь по координатам вершин: сумма xᵢyᵢ₊₁ − xᵢ₊₁yᵢ, а её знак — направление обхода. O(n) 2 задачи

Задачи

Блуждающий зуб Где встречаются отрезки Год по индикту Игрушечный RSA Простые в окне Самая длинная цепочка Коллатца Фибоначчи по модулю Взломать хеш Все остовные деревья Две монеты Нулевые ячейки факториала Произведения в ML-KEM Сколько раз выполнится строка Таблица Каннингема Числа Кармайкла в окне Штрихи на рейке Яблони в узлах сетки Прямые генератора Рулон кабеля Сколько оснований лгут

Часто рядом

безопасность 8 классика 8 олимпиады 6 случайность 3 в проде 3 многочлены 2 подсчёт вариантов 2 собеседования 2 разделяй и властвуй 2 битовые трюки 2 простые числа 2 карты и навигация 2