Иногда так бывает, что асимптотика решения задачи зависит от количества делителей числа во входе. Когда я только начинал заниматься спортивным программированием, я несколько раз слышал такое утверждение: «количество делителей числа n — это примерно кубический корень из n». И с самого начала я относился к этому факту с подозрением: неужели у чисел может быть так много делителей?

На самом деле, это, конечно, не так, но оценка в кубический корень дает нужный порядок величин для грубых оценок на числах, с которыми мы имеем дело в реальной жизни (отличие не больше, чем в 4 раза при n ≤ 10^15, и не больше, чем в 10 раз при n ≤ 10^18). Давайте разберемся, сколько все таки на самом деле делителей у чисел, и как этим пользоваться, а также придумаем новую более точную оценку.

https://telegra.ph/Ocenka-na-kolichestvo-delitelej-chisla-09-10