Блог пользователя onlydmc123

Автор onlydmc123, 10 лет назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор onlydmc123, 10 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

Автор onlydmc123, 10 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится