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

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

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

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

»
10 лет назад, # |
Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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