loverBoUy's blog

pth factor of a very large number
By loverBoUy, history, 2 years ago, In English

how to find pth factor of number n; example- n= 12 ,p= 3 factor of 12={1,2,3,4,6,12}; ans= 3;

constraints; n<=10^15; got tle in O(sqrt(n)); pls help

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

o(sqrt(n)) is the most optimal approach ig.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it -8 Vote: I do not like it

    Pollard's Rho (assuming that we are detecting primes with Miller-Rabin) gives an estimated time complexity of $$$O(n^\frac{1}{4})$$$.

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think I've done a problem that's the same as this; it passed TL in O(sqrt(n)).

Edit: the problem is 762A - k-th divisor, my submission 148662965

→ Reply