Алгоритм
Руста будет работать долго, если

мало, поэтому предлагаю небольшую модификацию.
Делим

на наибольшую возможную степень

. Если эта степень нечетна, то сразу стоп. Если же четна, то делаем то же самое для частного итд.
Думаю, что можно еще эффективнее.
Например, можно искать НОД частного и

Это сразу дает

для частного (без вычисления

и последующего деления) Но это имеет смысл делать, если степень частного больше степени

.