0w1

SPOJ

Fast Fourier Transform

Fast fourier transform can be applied on multiplication of polynomial functions, giving O( N lgN ) time complexity. One of the most common usage is for fast multiplication on big numbers. It exploits the property of the complex roots of un…