Блог пользователя loverBoUy

pth factor of a very large number
Автор loverBoUy, история, 21 месяц назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    21 месяц назад, # ^ |
    ← Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

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

    → Ответить
»
21 месяц назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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-й делитель, my submission 148662965

→ Ответить