Решение второй задачи по информатике отборочного тура http://nti-contest.ru/wp-content/uploads/7-%D0%91%D0%94.pdf

powers-02.py

# Константа, очень большое значение,
# будет намекать нам, что мы пока не знаем,
# как на самом деле представить какое-то число
# в виде оптимальной суммы
NONE = 1000000000

def solve(n, x):
  # Создаём пустой массив чисел из X + 1 ячеек,
  # так что storage[i] - сумма степеней для i
  storage = [NONE] * (x + 1)
  fill_powers(storage, n)
  fill_multiplications(storage)
  fill_sums(storage)
  return storage[x]

# Заполняем в массив все известные нам целочисленные корни
def fill_powers(storage, n):
  set_target(storage, n, 1)
  pow = 2
  while True:
    sqrt = int_sqrt(n, pow);
    set_target(storage, sqrt, pow);
    pow += 1
    if (sqrt == 1):
      break

# Функция вычисляет конкретный целочисленный корень степени pow из числа n
def int_sqrt(n, pow):
  for y in range(1, n + 1):
    if (y ** pow) <= n < (y + 1) ** pow:
      return y;

# Из уже заполненных значений находим все возможные произведения
# с оптимальным количеством корней
def fill_multiplications(storage):
  for i in range(2, len(storage)):
    for j in range(2, i):
      if (i % j == 0):
        set_target(storage, i,  storage[j] + storage[i / j])

# Вычисляем все доступные нам оптимальные суммы
# комбинируя уже найденные числа
def fill_sums(storage):
  for i in range(2, len(storage)):
    for j in range(1, i):
        set_target(storage, i, storage[j] +  storage[i - j])

# очень удобный вспомогательный метод - обновляет значение
# в массиве, если оно лучше старого
def set_target(storage, index, value):
  if (index < len(storage) and storage[index] > value):
    storage[index] = value

# Тут опущена работа со строками, это еще одна строчка нужна