Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Неправильный RSA

(Время: 3 сек. Память: 16 Мб Сложность: 64%)

Рома, Сережа и Андрюша решили улучшить знаменитый алгоритм шифрования RSA. Они решили, что в RSA в качестве модуля можно использовать в качестве числа n не только произведение двух простых чисел, но и произведение вида n = pkqk, где p и q – простые числа, а k – некоторое натуральное число.

Однако Коля указал, что помимо различных математических трудностей, новая схема может оказаться менее устойчивой к взлому. А именно, большое число, равное произведению двух различных простых чисел, тяжело разложить на множители, в частности, поскольку у него существует ровно одно нетривиальное разложение. А у числа вида n = pkqk их может быть больше. Например, у числа 100 = 22•52 есть целых восемь нетривиальных разложений на множители: 2•50, 2•2•25, 2•2•5•5, 2•5•10, 4•25, 4•5•5, 5•20 и 10•10.

Теперь Рома, Сережа и Андрюша думают – сколько же различных нетривиальных разложений на множители есть у числа n = pkqk?

Входные данные

Входной файл INPUT.TXT содержит число n (6 ≤ n ≤ 1018, гарантируется, что n = pkqk для различных простых p и q и натурального k).

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число — количество нетривиальных разложений на множители числа n.

Примеры

INPUT.TXTOUTPUT.TXT
161
21008

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ