Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

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

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

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru