Привет блог! Люди кто знает теорию чисел помогите. Задача: найти очень быстро количество делителей числа.
Я решал перебором до sqrt(n) но пишет Wrong Answer. Говорят, что нужно что–то быстрее, т.к. числа могут быть 10^18.
GD Star Rating
loading...
loading...
Вопервых, перебирав до sqrt(N) ты скорее всего забыл посчитать делители, которые больше sqrt(n), поэтому у тебя Wrong Answer, а не таймаут.
Вовторых, там вообще не просят найти количество делителей, там просят найти число с максимально возможным количеством делителей.
Если число является произведением простых p1n1p2n2 pknk, то количество его делителей равно, соответственно
n1n2 nk
Вопрос в том, сколько нужно взять pi и какие им приписать ni, чтобы произведение ni было максимально возможным, но произведение pini не превышало данного N.
Это находится не очень сложным алгоритмом (сложностью не больше O(log(N)^3)), дальше думай сам.
все делители <= sqrt(n), учат в школе, учат в школе, учат в школе.
задача разложения числа на делители на данный момент эффективно не решена. На этом, кстати, держится солидная часть криптографии вот уж лет 35 как. И, да, ты не совсем правильно понял задачу, Peels все правильно сказал.
Я знаю. Вот три способа решение этой задачи:
1. перебор всех чисел от 1 до sqrt(N)
2. роалгоритм или алгоритм Полларда
3. number field sieve.
(2|2) & (2 > sqrt(2)). Учат в школе, учат в школе, учат в шкооолее (заканчивает припев).
Кстати я наврал про количество делителей. Оно конечно же равно (n1+1)(n2+1) (nk+1)
ой. /*ушел в школу, ушел в школу, ушел в школу*/
Ещё метод ферма есть между 1 и 2
О, долбануться, Тимус на блоге! : )
Надо понимать, что WA это не время закончилось (TL), а именно что ответ лажовый.
Может быть, ты работаешь в 32битном типе и он у тебя переполняется?
типа там большие числа = отрицательные числа, ну как обычно
скорее всего так