Задача «Степень»

Question

Всем здравствуйте! Столкнулся с такой задачей:

Условие:
Для того чтобы проверить, как её ученики умеют считать, Мария Ивановна каждый год задаёт им на дом одну и ту же задачу — для заданного натурального ? найти минимальное натуральное ? такое, что ? в степени ? (?, умноженное на себя ? раз) делится на ?. От года к году и от ученика к ученику меняется только число ?. Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.

Входные данные:
Во входном файле содержится единственное число ? (1 ≤ ? ≤ 10^9) — на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы «завалить» кого-нибудь…).

Выходные данные:
Вывести единственное число ?.

Примеры:
Ввод 1:

Вывод 1:

Ввод 2:

Вывод 2:

Долго пытался решить задачу. Мой код с описаниями:

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)

Программа не проходит последний тест проверки. Помогите, пожалуйста, исправить ошибки в коде.

Answer 1

Вместо:

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 k != n//y: # n = k*y, где k - любое натуральное число
        n = k*y
        if fast_pow(n,n) % x == 0:
            print(n)
            break
        k+=1

Используйте вот это:

if a[0] != x:
    for i in range(40):
        if fast_pow(((i+1) * y), ((i+1) * y)) % x == 0:
            print((i+1) * y)
            break
else:
    print(a[0])

P.S. Как в комментариях было сказано, лучше используйте встроенный pow вместо fast_pow

Answer 2

elif len(b) >= 29:
    print(y)

Измени константу на 30 и все тесты пройдешь

БЛОГ НА HUSL

Задача «Степень»

Ответы (2 шт):