Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1324. Простое разложение
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 15/12/2009 | Сборы, группа 1 (2) |
| 27/02/2010 | Занятие 8 (C) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Положительное целое число может быть представлено в виде суммы различных простых чисел тем или иным способом.
Для заданных положительных целых чисел `N` и `K` вы должны подсчитать количество способов
разложения числа `N` на сумму `K` различных простых чисел.
При этом два разложения будем считать одинаковыми, если в них используется один и тот же набор простых чисел.
К примеру, число 8 может быть представлено как 3 + 5 или как 5 + 3, но эти разложения считаются одинаковыми.
Ваша задача – написать программу, вычисляющую количество разложений числа на сумму `K` различных простых чисел.
Например, при `N\ =\ 24` и `K\ =\ 3` ответом будет число 2, так как существует ровно два
разложения числа 24 на 3 простых числа: `24\ =\ 2\ +\ 3\ +\ 19` и `24\ =\ 2\ +\ 5\ +\ 17`.
В единственной строке ввода содержатся два целых положительных числа `N` и `K`, разделенных пробелом,
при этом `N\ ≤\ 1120` и `K\ ≤\ 14`.
Вывести единственное неотрицательное целое число – количество разложений числа `N` на сумму `K` различных
простых чисел.
Пример ввода 1
24 3
Пример вывода 1
2
Пример ввода 2
4 2
Пример вывода 2
0
