В Харьковской ЗКШ 2011 была задача http://pastebin.com/cZbTuvbg
Вот мой код по ней, который я оптимизировал как только мог http://pastebin.com/X9ah6Ee4
И это решение получает ТЛ.
Я предподсчитал корни из 1, все операции со степенями двойки заменил на битовые.

Если использовать тип float то WA из-за точности, но в тайм вкладывается.
На практике Фурье в модульной арифметике работает дольше, так что пишу в комплексных числах.

Что еще можно оптимизировать в коде? Может что-то кардинально поменять?
Может я делаю какие-то лишние операции?