an6285's blog

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

| Write comment?
»
7 years 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.

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice problem! Thanks for sharing.