Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
SumOfPowers

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


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"