В этой задаче нам нужно уметь делать:
1 - Факторизацию числа
2 - Проверку числа на простоту
3 - Быстрое(бинарное) возведение в степень
#1 Факторизация числа – это представление числа в виде произведений простых чисел.
Пример: 100 = 2^2 * 5^2.
Теперь, если мы знаем факторизацию числа, то легко найти и количество его делителей.
Количество делителей равно произведению всех (степеней+1) в факторизации числа.
Если N = pr1^deg1 * pr2^deg2 * pr3^deg3 * … * prK^degK, то количество делителей равно (deg1 + 1) * (deg2 + 1) * (deg3 + 1) * … * (degK + 1), т.к. каждый множитель может входить в N со степенями от 0..deg_i.
Допустим N = 2^3 * 3^2 * 5^2, тогда количество делителей равно (3+1) * (2 + 1) * (2 + 1) = 36.
Обычная факторизация делается за O(√N).
Псевдокод:
Number_of_divisors = 1;
While (divisor^2 ≤ N)
{
Deg = 0;
While (N mod divisor = 0)
{
N /= divisor;
Deg++;
}
Number_of_divisors *= Deg + 1;
}
If (N > 1)
Number_of_divisors *= 2;
Единственная проблема в задаче – N большое число.
Т.к. обычная факторизация работает за O(√N), а у нас N ≤ 10^18 – то программа получит TLE
Что будем делать?
Модифицируем факторизацию до O(∛N).
А именно будем перебирать делитель от 2 до ∛N, и делить пока делится.
В один момент, когда divisor^3 > N, то останавливаемся и делаем вот что:
Т.к. divisor^3 > N, значит, N состоит из двух или одного множителя, больших divisor:
-
Либо N – большое простое число, тут ответ умножается на 2
-
Либо N = pr1 * pr2, тут ответ умножается на 4 (на 2 от первого и опять на 2 от второго)
-
Либо N = x * x = x^2, тут ответ умножается на 3.
#2 Проверка числа на простоту:
Если N не такое уж большое, то можно перебрать все делители от 2 до √N, в противном случае воспользоваться приложением функции Эйлера, а именно:
Самое известное и важное свойство функции Эйлера выражается в теореме Эйлера:
где 
и 
взаимно просты.
Функция Эйлера 
или 
— это количество чисел от 1 до 
, взаимно простых с .
В частном случае, когда простое, теорема Эйлера превращается в так называемую малую теорему Ферма:
Подставим под наше число N, и для случайного проверим, что a^(N-1) = 1 (mod N):
Возведем в степень N-1 по модулю N.
Если ответ 1, то N простое, иначе составное.
Для уверенности проделаем всё это 50 раз (возьмём 50 случайных ).
И если хоть раз a^(N-1) ≠ 1 (mod N), то N составное.
#3 Бинарное возведение в степень – ссылка - http://e-maxx.ru/algo/binary_pow