Теория чисел на Высшей пробе

Подсказка 1

Хочется как-то в общем виде записать, чему равно произведение всех делителей. Мы знаем, что в большинстве случаев делители можно разбить на пары (потому что если у числа n есть делитель k, то есть также делитель n/k), но у некоторых чисел есть лишь нечетное количество делителей. Что это за числа?

Подсказка 2

Если число является точным квадратом, то оно имеет нечётное число делителей! Подойдёт ли нам какой-то из точных квадратов?

Подсказка 3

Пусть у точного квадрата n кроме делителя √n есть еще s пар делителей. Заметим, что произведение делителей в каждой паре равно n, тогда произведение всех делителей равно n^(s+1/2) = n³, а это верно только при n = 1.

Подсказка 4

Теперь рассматриваем числа, имеющие s пар делителей, чему равно произведение делителей в этом случае? Можем ли мы понять, сколько делителей должно быть у нашего числа?

Подсказка 5

Так как n^s = n³, у нашего числа есть всего 6 делителей! Давайте попробуем понять, сколько простых чисел может быть делителями числа n, может ли у n быть больше двух простых делителей?

Подсказка 6

Нет, у n есть максимум два простых делителя! Ведь если бы n делилось на р₁, р₂ и р₃, то у него были бы делители р₁р₂, р₁р₃ и р₂р₃, а так как делителей всего шесть, среди этих чисел есть число 1, что невозможно, ведь 1 не является простым числом. Таким образом, мы можем разложить n на простые множители и перебрать все возможные варианты.

Подсказка 7

Получаем, что n = p⁵ или n = р₁р₂². В первом случае легко угадываем пятую степень некоторого числа, не превосходящую 100, а во втором вариантов будет гораздо больше! Так как р₁ ≥ 2, р₂² ≤ 100/2 = 50, отсюда получаем возможные варианты р₂, перебираем их и находим подходящие числа!