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