Всем здравствуйте! Столкнулся с такой задачей:
Условие:
Для того чтобы проверить, как её ученики умеют считать, Мария Ивановна каждый год задаёт им на дом одну и ту же задачу — для заданного натурального 𝐴
найти минимальное натуральное 𝑁
такое, что 𝑁
в степени 𝑁
(𝑁
, умноженное на себя 𝑁
раз) делится на 𝐴
. От года к году и от ученика к ученику меняется только число 𝐴
.
Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.
Входные данные:
Во входном файле содержится единственное число 𝐴
(1 ≤ 𝐴 ≤ 10^9
) — на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы «завалить» кого-нибудь…).
Выходные данные:
Вывести единственное число 𝑁
.
Примеры:
Ввод 1:
8
Вывод 1:
4
Ввод 2:
1
Вывод 2:
1
Долго пытался решить задачу. Мой код с описаниями:
Python
from sys import setrecursionlimit
setrecursionlimit(10**9) # увеличение максимальной глубины рекурсии
def fast_pow(a, n): # функция быстрого возведения в степень
if n == 0:
return 1
elif n == 1:
return a
elif n % 2 != 0:
return a * fast_pow(a, n-1)
elif n % 2 == 0:
return fast_pow(a*a, n/2)
def decomp(n): # функция разложения числа на простые множители
ans = []
d = 2
while d * d <= n:
if n % d == 0:
ans.append(d)
n //= d
else:
d += 1
if n > 1:
ans.append(n)
return ans
x = int(input())
a = list(set(decomp(x))) # разложение числа x на простые множители в единственном экземпляре
b = decomp(x) # разложение числа x на простые множители
y = 1
for i in range(len(a)): # перемножение простых множителей
y *= a[i]
k = 1
n = k*y
if x == 1: # если x = 1, то и n = 1
print(1)
elif len(b) >= 29: # 29 - потому что хотя бы 2**30 уже будет более 10**9, что противоречит условию задачи
print(y) # тогда y**y уже будет делится на n
else:
while pow(n,n,x) != 0:
n = k*y
k += 1
print(n)
Программа не проходит последний тест проверки. Помогите, пожалуйста, исправить ошибки в коде.