Семинар 10. Разное (Алгоритмы и структуры данных, часть 1)

Сжатие координат: простой пример задачи, идея метода. Реализация: сортировка бин. поиск или использование std::map. Алгоритм Евклида для поиска gcd, время работы, реализация. Приведение дробей к нормальному виду. Модифицированный алгоритм Евклида (идея). Быстрое (бинарное) возведение в степень: идея, пример кода. Применения: обратный по модулю, перемножение матриц. Количество маршрутов и маршрут минимального веса в графе среди всех маршрутов с фиксированным количеством рёбер. Дерево Фенвика. Интерфейс.