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

Автор sky_full_of_stars, история, 3 года назад, По-английски

I was trying to solve this bugaboo on SPOJ.

My approach is fairly simple. I pre-calculate all prime numbers, smallest prime factor, and all divisors in sieve() first.

Then for each i in [1,maxN) I calculate the number of divisors for each 'i' and verify if its a valid number in O(1).

total complexity is : O(N log(log N))) for sieve + O(N log(N) to check number of divisors

My solution which TLE'd.

I'm not able to figure out what I'm missing here. Can someone please help me with this?

Thanks!

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