OmaeWaMouShenDeiru's blog

Another math problem
By OmaeWaMouShenDeiru, 10 years ago, In English

hello,

for this problem, all I could come up with is to find all divisors of 'b' that are less than or equal to 't' using O(sqrt(n)) but It will get TLE for such input limits " < (1<<54)".

any hints for a better aproach ?

thanks :D

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem link is broken...

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

    link is fixed :D

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

      Why would it get TL? 2^27 can fit time limit of 1 second in some cases, but there I even see 3 second limit, so I think it should pass easily.

      Otherwise if you want to have faster solution you can try to factorize faster. You can use pollard's pollard's factorizing algo that works in O(sqrt(least divisor)) and divides you N as multiplication of two numbers.(if I remember it right, I used it only once in my life by far)

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

Note: I see in "best submissions" list people that have solved the problem in 0.0 time, so perhaps there is some much better solution, but you can still get AC with mine.

Okay, so this is indeed a factorization problem. My solution may not be the simplest, but it should teach you some tricks to finding divisors quite quickly.

Operations "/" and "%" are slow. That's just how it is. They're significantly slower than "+" or "*", so if you were to perform 2^27 of them, it's quite normal to time limit. So let's come up with a better method now — let's find only the prime divisors of the number. Now you may ask "how is that faster, it's still O(sqrtN)?" — this is true, but we can check if some number is a prime factor only if it is prime, which reduces tons of operations. So we first use the Sieve of Eratosthenes to find all primes under 2^27, and then we can relatively quickly find the prime factorization of our number.

A trick to speed it up, is each time you find a divisor — divide the number by it, this way the number will become smaller, and it's square root would also reduce, giving you less iterations in the process. Of course this wouldn't work on all numbers, since factorizating a prime would always require the same amount of operations.

Finally, now that we've got our prime factorization, we can just generate all divisors! That's right, the divisors are actually not that many at all, most likely a few millions at most. So a clever generator can generate them all in linear time.

Here is my AC code in 1.51s

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

    Thank you so much for precuios informations.

    I know all about prime factorization method along with Sieve of Eratosthenes, but I didn't know how to generate all divisors using prime factors.

    I don't want to look at any AC codes until I get it my self, but if you can give any hints for generating all divisors from prime factors, it will be appreciated. :D

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

      Well, generating them is quite simple. All you have to do is be careful not to repeat.

      Now suppose you have K factors. Then the easiest way to go is to just generate all 2^K combinations, but this gives repetitions, because you might have one prime factor more than once.

      Simplest way to overcome that would be to group the equal prime divisors together, and then just try all possible combinations of how much you take from each group.

      Example:

      Say you have number 72=2*2*2*3*3. Then you say you have 3 twos and 2 threes. Then just try taking 2^0;3^0 | 2^0;3^1 | 2^0;3^2 | 2^1;3^0 etc...

      In this way you will not repeat a divisor, and therefore get a linear running time :)

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

        well it's weird how the judges time works out with this code.

        I got AC with 1.78 S.

        Thank you so much :D Enchom

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

        I sent my code again but with upper limit for Sieve equal to (1 << 20)

        and surprisingly I got AC with 0.0 S :V

        I don't know if it is a problem with weak test cases or if this limit is quite enough for this problem.

        → Reply