an6285's blog

By an6285, history, 2 weeks 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  

»
2 weeks 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.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice problem! Thanks for sharing.