Дано натуральное число А. Найти такое минимальное натуральное N, что N^N делится на А без остатка.

Question

Как решить задачу боле рациональным способом, чем просто тупым подбором?

Answer 1

Любое натуральное число представимо в виде произведения простых чисел в степенях. Если А простое, то сразу - минимальное А^А. Иначе подобрать степени в разложении А . Лт лбратного. Т. е. Взять А^А и пытаться сократить, так, чтоы показатели были не меньше, чем для А. и в основании и показателе было одно и то же число (с учётом кратности показателя) . Даже прямой перебор резко сократится.