Задача 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
|
