an6285's blog

By an6285, history, 6 months ago, In English,

Facing a lot of difficulty in solving this problem from a long time. Problem Link-SAS002. Naive approach O(sqrt(n)) clearly times out. How to solve this problem in given time limit and what is the intended time complexity of the algorithm? Thought about finding number of divisors in O(n^(1/3)) and using that, after some research.Is that correct approach?

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Yes, it seems to be the correct approach. This blog describes how to count number of divisors of a a number in O(N1 / 3) and this gives a proof that product of all divisors of N is Nd / 2 where d is the number of divisors of N.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your reply. I will try to solve it out.

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice problem! Thanks for sharing.