Математика: различия между версиями
Материал из Algocode wiki
NekoKarp (обсуждение | вклад) (Добавлена ссылка на статью) |
KiKoS (обсуждение | вклад) м |
||
| (не показано 6 промежуточных версий 2 участников) | |||
| Строка 10: | Строка 10: | ||
* [[Расширенный алгоритм Евклида]] | * [[Расширенный алгоритм Евклида]] | ||
* [[Решето Эратосфена]] | * [[Решето Эратосфена]] | ||
| + | * [[Решето Эратосфена#Линейное время работы|Линейное решето Эратосфена]] | ||
* [[Бинарное возведение в степень]] | * [[Бинарное возведение в степень]] | ||
* [[Малая теорема Ферма]] | * [[Малая теорема Ферма]] | ||
| + | * [[Диофантово уравнение]] | ||
* [[Обратный элемент по модулю]] | * [[Обратный элемент по модулю]] | ||
| + | * [[Обратный по модулю]] | ||
* [[Китайская теорема об остатках]] | * [[Китайская теорема об остатках]] | ||
* [[Тест Миллера - Рабина для проверки на простоту]] | * [[Тест Миллера - Рабина для проверки на простоту]] | ||
| + | * [[Обратные ко всем остаткам за O(p)]] | ||
==Комбинаторика== | ==Комбинаторика== | ||
| Строка 24: | Строка 28: | ||
==Теория игр== | ==Теория игр== | ||
| − | ==Быстрое преобразование Фурье | + | ==Комплексные числа== |
| + | * [[Комплексные числа]] | ||
| + | |||
| + | ==Свёртки== | ||
| + | * [[Быстрое преобразование Фурье]] | ||
| + | * [[Длинная арифметика]] | ||
| + | * [[Преобразование Адамара]] (xor-свёртка) | ||
==Матроиды== | ==Матроиды== | ||
* [[Что такое матроид]] | * [[Что такое матроид]] | ||
| + | * [[Нахождение базиса матроида]] | ||
Текущая версия на 17:57, 5 ноября 2020
Содержание
Базовая математика
Теория чисел
- Проверка на простоту за корень
- Факторизация за корень
- Модульная арифметика
- Алгоритм Евклида
- Расширенный алгоритм Евклида
- Решето Эратосфена
- Линейное решето Эратосфена
- Бинарное возведение в степень
- Малая теорема Ферма
- Диофантово уравнение
- Обратный элемент по модулю
- Обратный по модулю
- Китайская теорема об остатках
- Тест Миллера - Рабина для проверки на простоту
- Обратные ко всем остаткам за O(p)