Параллель А СПБ: различия между версиями
Материал из Algocode wiki
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 13: | Строка 13: | ||
* [[Быстрая факторизация алгоритмом Полларда Ро]] | * [[Быстрая факторизация алгоритмом Полларда Ро]] | ||
* [[Китайская теорема об остатках]] | * [[Китайская теорема об остатках]] | ||
| + | |||
| + | ==2. Оптимизации динамики== | ||
| + | * [[Монотонность точки перегиба]] | ||
| + | * [[Divide&Conquer оптимизация]] | ||
| + | * [[Оптимизация Кнута]] | ||
| + | * [[Convex hull trick]] | ||
| + | * [[Дерево Li Chao]] | ||
| + | * [[Лямбда-оптимизация]] | ||
| + | * [[MOD**2-оптимизация|$\text{MOD}^2$-оптимизация]] | ||
| + | |||
| + | ==3. Геометрия== | ||
| + | * [https://algocode.ru/files/course_aspb2019/main.pdf Конспект по геометрии] | ||
Текущая версия на 07:16, 13 октября 2019
1. Теория чисел
- Бинарное возведение в степень
- Малая теорема Ферма
- Теорема Эйлера
- Обратный по любому модулю в 2 строчки
- Алгоритм Евклида
- Расширенный алгоритм Евклида
- Обратные ко всем остаткам за O(p)
- Решето Эратосфена
- Тест Миллера - Рабина для проверки на простоту
- Быстрая факторизация алгоритмом Полларда Ро
- Китайская теорема об остатках
2. Оптимизации динамики
- Монотонность точки перегиба
- Divide&Conquer оптимизация
- Оптимизация Кнута
- Convex hull trick
- Дерево Li Chao
- Лямбда-оптимизация
- $\text{MOD}^2$-оптимизация