For this problem on spoj: http://www.spoj.com/problems/ODDDIV/
Code Removed After AC :D
I went through the following steps to solve it: 1_ generate all primes to sqrt(1^10) to use them in prime factorization
2_ pre calculate number of divisors for numbers in range (1 — 100000)
3_ answer each query in O(n) time, I found that only perfect square numbers have odd number of divisors, so I only need to check if(fact_num[i] == k)from x to sqrt(y)
Any help to improve my time ??
First of all, when you compute factnum[i], you can calculate the number of divisors only for i, because if i = p1d1 * p2d2 * ... * pkdk, the number of it's divisors is (d1 + 1) * (d2 + 1) * ...(dk + 1), but for i * i the number of divisors is (2 * d1 + 1) * (2 * d2 + 1) * ...(2 * dk + 1).
Another optimization is based on the fact that K < 10000. So, you can divide the numbers in range [1, 100000] in sets, where Set[i] = {k|factnum[k] = = i}. You can find the answer for a query with binary search on Set[K].
for the array fact_num[i],I calculate the number of divisors for i*i depending on the fact that only perfect squares has odd number of divisors and I save the answer in position 'i'
Isn't true for this problem ??
It is true, but using the fact that if you know the factorization for i, you can make the transition to i * i, it's faster to compute the factorization only for i :)
Ok now i got the idea and it is super fast.
I'll try it and see the result, Thank you :D
It is Accepted and with 0.83 S
I learned something new, thank you so much :D