onlydmc123's blog

By onlydmc123, 10 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By onlydmc123, 10 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it

By onlydmc123, 10 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it