@mikelll

Нужно узнать количество делителей числа N.
Но сложность в том что N большое и перебирать все делите не вариант.

0

@diagon

Насколько большое N?
Как вариант, простейший алгоритм за O(sqrt(n)).
Будет укладываться в секунду для чисел примерно до 10^13. Более быстрые алгоритмы уже не так тривиальны.

1

@mikelll

Да вот 1 <= n <= 10^18
и тут по ходу в никакие типы не влезает =(

0

@JlightenDev_C++

unsigned long long n;

0

@diagon

Ну, тут мне уже писать код не хочется, но алгоритм мне видится таким: берем какой-нибудь быстрый алгоритм факторизации со сложностью O(n ^ (1/3) ) или быстрее, и затем, зная факторизацию, можно с помощью комбинаторики подсчитать количество делителей.

0

@Dani

Для решения данной задачи мы воспользуемся одной из теорем комбинаторики.

Теорема. Если существует K классов, содержащих соответственно n1 , n2 , . . . nK элементов, то число различных способов выбора элементов равно (n1 + 1)(n2 + 1)...(nK + 1)

Для определенности рассмотрим на примере. В коробке лежат 10 шаров синего, 8 красного и 5 желтого цветов. Сколькими способами можно достать данные шары из коробки? Разумеется, что все шары доставать необязательно, например, можно достать 2 синих, 4 желтых и 3 красных шара, или 1 синий и 5 желтых. А ведь можно и вообще их не доставать, этот случай тоже является случаем выбора шаров, в результате которого получается пустое множество выбранных элементов.

Для ответа на этот вопрос следует воспользоваться вышеприведенной теоремой. Мы имеем три класса:
Шары синего
Желтого
Красного цветов

Число элементов первого класса равно 10, второго - 8, третьего, соответственно, 5. Тогда общее количество возможных вариантов выбора будет равно S = (10 + 1)(8 + 1)(5 + 1) = 594. То есть число различных способов выбора шаров из коробки равно 594.

Эту задачу можно было бы решать и методом полного перебора, что значительно увеличит время выполнения программы.

Теперь проведем аналогию между нашей задачей и задачей про шары. Основная теорема арифметики гласит, что любое натуральное число можно представить в виде произведения простых чисел, входящих в разложение данного числа в различных степенях. Классом в нашем случае является простое число. Количеством элементов - степень, в которой это число входит в разложение.

Тогда для решения задачи необходимо разложить число x на простые множители, посчитать сколько раз встречается каждое простое число в разложении и перемножить соотвествующие результаты в соответствии с вышеприведенной формулой.


Взял с acmp.ru могу показать код, только он на паскале.

1

@ShuricFC

а что значат эти две строчки? res += 2 - (i *i == n);

return res + 2 - (n == 1);

0

zer0mail

Дату постов посмотрите.

0