Задача №3208. Делители
Натуральное число \(a\) называется делителем натурального числа \(b\), если \(b = ac\) для некоторого натурального числа \(c\). Например, делителями числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно просты, а 18 и 24 — нет.
Будем называть нормальным набор из \(k\) чисел (\(a_1, a_2, \ldots, a_k\)), если выполнены следующие условия:
- каждое из чисел \(a_i\) является делителем числа \(n\);
- выполняется неравенство \(a_1 \lt a_2 \lt \ldots \lt a_k\);
- числа \(a_i\) и \(a_{i+1}\) для всех \(i\) от \(1\) до \(k - 1\) являются взаимно простыми;
- произведение \(a_1a_2\ldots a_k\) не превышает \(n\).
Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360.
Требуется написать программу, которая по заданным значениям \(n\) и \(k\) определяет количество нормальных наборов из \(k\) делителей числа \(n\).
Первая строка входного файла содержит два целых числа: \(n\) и \(k\) (\(2 \le n \le 10^8\), \(2 \le k \le 10\)).
В выходном файле должно содержаться одно число — количество нормальных наборов из \(k\) делителей числа \(n\).
Правильные решения для тестов, в которых \(n \le 1000\) и \(k = 2\), оцениваются из 30 баллов.
Правильные решения для тестов, в которых \(k = 2\), оцениваются из 60 баллов (в эти баллы включаются также 30 баллов для случая \(n \le 1000\), \(k = 2\)).
90 3
16
10 2
4