Can someone help me? In Discussion people said they solved in O(m*logn), is there O(n+m) solution too? If you can, give me ideas of both solutions. http://acm.timus.ru/problem.aspx?space=1&num=1987

Thanks

I was searching a lot to understand FFT, I know FFT has many applications, but I need it for multiplying polynomials. I Found this: http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/lectures/lect0423.txt. and it was really helpful to understand its nature, there is given algorithm in pseudo-C too, but I don't know how to implement it in C or C++. Can you suggest to me clean impelementation of FFT, where the inputs are two polynomials and output is multiplication of them?

Thanks in advance.

I know that you can use sieve of Eratosthenes for finding all prime numbers in (1,N) interval, but can you suggest algorithm that can do that for (N,M) interval, when N,M are large, for instance 10^9 and N=500,000,000; M=501,000,000.