Задача на теорию чисел (python) (есть код на pascal)

Question

Задача звучит следующим образом:

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

Требуется решение на Python. Есть работающий код на Pascal, но из меня знаток Паскаля, как из моей кошки бармен.

function GetSmplNums(n: integer; from: integer): List<(integer,integer)>;
begin
  Result := new List<(integer, integer)>;
  var i := from;
  repeat
    if n mod i = 0 then
    begin
      var c := 0;
      
      repeat
        c += 1;
        n := n div i;
      until n mod i <> 0;
      
      Result += (i, c);
    end;
    
    i += 1;
  until i*i > n;
  
  if n <> 1 then
    Result += (n, 1);
end;
 
begin
  var l := GetSmplNums(ReadlnInteger,2);
  var min_exp := l.Max(t->t[1]);
  var n := 1;
  foreach var t in l do
    n *= t[0];
  var res := n;
  while res < min_exp do
    res *= n;
  res.Print;
end.

Вот решение на Питоне, но оно работает слишком долго.

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)))

y = 1
for i in a:
    y *= i

if x == 1:
    print(1)
elif 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])

Answer 1

Решение нашёл. Привожу код.

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())
if x == 1:
    print(1)
else:
    a = list(set(decomp(x)))
    b = decomp(x) 
 
    y = 1
    for i in range(len(a)): 
        y *= a[i]
    k = 1
    n = k*y
 
    if a[0] != x:
        for i in range(40):
            t = (i+1)*y
            if pow(t, t, x) == 0:
                print((i+1) * y)
                break
    else:
        print(a[0])

Answer 2

решал немного по-другому, и пока не могу найти ошибку код:

def fact(n):
   p = {}
   d = 2
   while d*d <= n:
       while n % d == 0:
           if d in p:
               p[d] += 1
           else:
               p[d] = 1
           n //= d
       d += 1
   if n > 1:
       p[n] = 1
   return p
from math import sqrt
n = int(input())
s = fact(n)
k = 1
step = [int(i) for i in s.keys()]
for i in range(len(step)):
    if s[step[i]]%2 != 0:
        s[step[i]] += 1
    k = k*(step[i]**s[step[i]])
print(int(sqrt(k)))

БЛОГ НА HUSL

Задача на теорию чисел (python) (есть код на pascal)

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