Для решения этой задачи нам потребуются некоторые математические
знания. Любое число можно представить в виде двух наборов чисел: один из них - его простые делители,
другой в каждом элементе содержит степень этого делителя. Т.е. числу 12 будет соответствовать набор
((2, 3), (2, 1)) - 12 = 22 * 31.
Чтобы число (X) делилось на другое число (Y) необходимо, чтобы для каждого простого делителя степень
этого делителя у числа X была больше либо равна степени того же простого делителя у числа Y.
Для начала разобьем число A на простые делители. Заведем два массива, в первом будем хранить
значения простых делителей, а во втором - их степени (назовем этот массив k). Будем считать, что
число 1 встречается 1 раз - занесем это до начала цикла, это поможет избежать отдельной обработки
числа 1. Устроим цикл (i) от 2 до A и будем считать, какие и сколько делителей встречается.
При правильном выполнении этих операций мы получим два массива, по которым можно однозначно
восстановить число.
Теперь посчитаем число K из которого затем будем получать число N. Т.к. в составлении числа N должны
присутствовать все простые делители, которые имеет число A, то K будет равно произведению всех
простых делителей числа A со степенью 1. Т.е. числу K будет соответствовать тот же массив простых
делителей, что и числу A, а все их степени будут равны 1.
Устроим цикл (j) от 1 до A, в котором будем перебирать "дополнительный множитель" для
числа K. Т.е. мы получаем рабочее N = K * j. Разобьем j на том же наборе простых делителей на
степени (назовем этот массив nk) и проверим следующее условие: если для всех делителей (nk[i] + 1) *
K * j >= k[i], то выводим число K * j - это и будет ответ, иначе переходим к следующему шагу
цикла по j.
По заданному числа A необходимо найти минимальное N, такое, что N^N кратно A
Для того чтобы проверить, как её ученики умеют считать, Мария Ивановна каждый год задаёт им на дом одну и ту же задачу – для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году и от ученика к ученику меняется только число A.
Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.
Входные данные
Во входном файле содержится единственное число A (1 ≤ A ≤ \(10^9\) – на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы «завалить» кого-нибудь…).