Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1534. Делители
Рекурсивный переборСокращение перебора с помощью идеи
Олимпиадные задачи на русском языке
| 23/01/2011 | Областная олимпиада школьников по информатике. II тур. (7) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Натуральное число `a` называется делителем натурального числа `b`, если `b\ =\ "ac"`
для некоторого натурального числа `c`. Например, делителями
числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно
простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно
просты, а 18 и 24 — нет.
Будем называть нормальным набор из `k` чисел (`a_1,\ a_2,\ …,\ a_k`),
если выполнены следующие условия:
- каждое из чисел `a_i` является делителем числа `n`;
- выполняется неравенство `a_1\ <\ a_2\ <\ …\ <\ a_k`;
- числа `a_i` и `a_{i+1}` для всех `i` от 1 до `k\ –\ 1` являются взаимно простыми;
- произведение `a_1*a_2*…*a_k` не превышает `n`.
Например, набор (2, 9, 10) является нормальным набором из 3 делителей
числа 360.
Требуется написать программу, которая по заданным значениям `n` и `k` определяет
количество нормальных наборов из `k` делителей числа `n`.
Формат входного файла
Первая строка входного файла содержит два целых числа: `n` и `k` (`2\ ≤\ n\ ≤\ 10^8`,
`2\ ≤\ k\ ≤\ 10`).
Формат выходного файла
В выходном файле должно содержаться одно число — количество нормальных наборов из `k` делителей числа `n`.
Пример ввода 1
90 3
Пример вывода 1
16
Пример ввода 2
10 2
Пример вывода 2
4
Примечание
Правильные решения для тестов, в которых `n\ ≤\ 1000` и `k\ =\ 2`, оцениваются
из 30 баллов.
Правильные решения для тестов, в которых `k\ =\ 2`, оцениваются из 60 баллов
(в эти баллы включаются также 30 баллов для случая `n\ ≤\ 1000`, `k\ =\ 2`).
Источник: региональный этап Всероссийской олимпиады по информатике 2010/2011, http://neerc.ifmo.ru/school/ 