OmaeWaMouShenDeiru's blog

Prime factorization problem spoj ODDDIV
By OmaeWaMouShenDeiru, 10 years ago, In English

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 ??

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

»
10 years ago, # |
← Rev. 5   Vote: I like it +1 Vote: I do not like it

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].

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ??

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 :)

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok now i got the idea and it is super fast.

        I'll try it and see the result, Thank you :D

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        It is Accepted and with 0.83 S

        I learned something new, thank you so much :D

        → Reply