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

10^18 prime factorisation...??
Автор vsanjay_nitdgp, история, 9 лет назад, По-английски

could any one post code for the followong question.

PROBLEM :F ,GYM

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

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

This question is pretty simple if you have Pollard Rho algorithm in your library. It's a straight copy and paste.

Here you go :

http://ideone.com/3dnYAv

Note: I think there is some way ( which I don't know ) to solve this question without this algorithm.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Blog Post

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

First remove all prime factors that are less than 10^6. Let x be the resulting number. Now check if x is prime or not using miller-rabin. If it is prime then we already have the prime factorization. If x is not prime we know that the remaining prime factors are greater than 10^6, therefore it must have exactly two prime factors (since having 3 or more would yield a number greater than 10^18). Now we need to know whether those prime factors are equal or not, we can simply check if x is a square or not, we can do this be testing if x == pow(int(sqrt(x) + .5), 2). With these you should be able to get the number of divisors.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Correct me if I'm wrong, but isn't miller rabin unreliable especially for programming contests?

    → Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Is it garanteed that x == pow(int(sqrt(x) + .5), 2) works for every case (precision loss)?? I remember doing something similar and getting wrong answer, so I just iterated from sqrt(x)-5 till sqrt(x)+5 to avoid that, though probably sqrt(x) and sqrt(x)+1 are enough.

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

here is a recent blog post by himanshujaju.

→ Ответить