Задача SumOfPowers
Некоторые натуральные числа (например, 9=32) сами являются квадратами натуральных чисел; некоторые (например, 17=42+12) можно представить как сумму двух квадратов; некоторые (например, 6=22+12+12) — только как сумму минимум трех квадратов; и так далее. Аналогичные подсчеты можно проводить не только для квадратов, но и для других степеней. Например, 17 не является кубом натурального числа и не может быть представлено суммой двух кубов, но может быть представлено суммой трех, как 23+23+13. Напишите программу, определяющую, в сумму какого минимального количества K-ых степеней натуральных чисел можно разложить каждое из чисел N1, N2, …, NM.
Технические условия:
Программа должна прочитать с клавиатуры сначала показатель степени K (1≤K≤98), затем количество чисел M (1≤M≤9876), для которых нужно найти минимальные количества, затем сами числа N1, N2, …, NM (каждое 1≤Ni≤987654). Все числа записаны в одной строке и разделены одинарными пробелами. Программа должна вывести на экран в одну строку M разделенных пробелами чисел — минимальные количества K-ых степеней натуральных чисел, в сумму которых можно разложить числа N1, N2, …, NM.
Пример 1:
Ввод: 2 3 9 17 6
Вывод: 1 2 3
Пример 2:
Ввод: 3 3 9 17 6
Вывод: 2 3 6