Фурье и длинка (6 мая 2016)

1. Длинная арфиметика
1. Многочлены ↔ длинные целые неотрицательные числа
2. Длинные числа → длинные вещественные числа, числа со знаком
3. Хранение длинных чисел: vector<int>; int num[N];
4. Сложение, вычитание, сравнение, умножение и деление на короткое (код умножения на короткое)
5. Алгоритмы для умножения многочлены/чисел: квадрат, Карацуба, Фурье (код умножения за квадрат)
6. Деление и умножение многочленов за O(nm) (код деления)
7. Двоичная арифметика: умножение, деление
8. Двоичная арифметика: gcd чисел за O(nm)

1. Деление чисел.
1. Бинпоиск за O(nm(n-m)/k²),
2. Бинпоиск по цифре за O(nm/k)
3. Честное деление за O(nm/k²).
2. Быстрое деление
1. Числа: разделяй и властвуй за O(nlog²n).
2. Многочлены: фокус с рядами за O(nlog²n).
3. [skipped] Числа: метод Ньютона за O(nlogn).
4. [skipped] Все идеи обобщаются на извлечение корня
5. [skipped] Многочлены: O(nlogn).
3. Фурье
1. [homework] Повышаем точность
2. [homework] Деление на 3 части, k частей.
3. [homework] По простому модулю.
4. [skipped] Предподсчёт корней. Как быстро и точно посчитать?