Привет блог! Люди кто знает теорию чисел помогите. Задача: найти очень быстро количество делителей числа.

Я решал перебором до sqrt(n) но пишет Wrong Answer. Говорят, что нужно что–то быстрее, т.к. числа могут быть 10^18.

GD Star Rating
loading...

9 Responses to Нужно найти очень быстро количество делителей числа

  1. Peels:

    Во–первых, перебирав до sqrt(N) ты скорее всего забыл посчитать делители, которые больше sqrt(n), поэтому у тебя Wrong Answer, а не таймаут.

    Во–вторых, там вообще не просят найти количество делителей, там просят найти число с максимально возможным количеством делителей.
    Если число является произведением простых p1n1p2n2…pknk, то количество его делителей равно, соответственно
    n1n2…nk

    Вопрос в том, сколько нужно взять pi и какие им приписать ni, чтобы произведение ni было максимально возможным, но произведение pini не превышало данного N.

    Это находится не очень сложным алгоритмом (сложностью не больше O(log(N)^3)), дальше думай сам.

  2. DaOn:

    все делители <= sqrt(n), учат в школе, учат в школе, учат в школе.

  3. DaOn:

    задача разложения числа на делители на данный момент эффективно не решена. На этом, кстати, держится солидная часть криптографии вот уж лет 35 как. И, да, ты не совсем правильно понял задачу, Peels все правильно сказал.

  4. AhDummy:

    Я знаю. Вот три способа решение этой задачи:

    1. перебор всех чисел от 1 до sqrt(N)
    2. ро–алгоритм или алгоритм Полларда
    3. number field sieve.

  5. Peels:

    (2|2) & (2 > sqrt(2)). Учат в школе, учат в школе, учат в шкооолее (заканчивает припев).

  6. Peels:

    Кстати я наврал про количество делителей. Оно конечно же равно (n1+1)(n2+1)…(nk+1)

  7. DaOn:

    ой. /*ушел в школу, ушел в школу, ушел в школу*/

  8. Moun:

    Ещё метод ферма есть между 1 и 2

  9. Si:

    О, долбануться, Тимус на блоге! : )

    Надо понимать, что WA — это не время закончилось (TL), а именно что ответ лажовый.
    Может быть, ты работаешь в 32–битном типе и он у тебя переполняется?
    типа там большие числа = отрицательные числа, ну как обычно
    скорее всего так

Добавить комментарий