Теоретический материал: алгоритм Карацубы и быстрое преобразование Фурье (А.Климовский)
Разбор задач
В рассматриваемых задачах БПФ (или алгоритм Карацубы) используется не как вспомогательный инструмент для длинной арифметики, а для перемножения многочленов, которое может быть видно не сразу. Это обусловлено тем, что задачи на длинную арифметику сами не представляют теоретического интереса.