Задача C. Делители
Первоисточник: Всероссийская олимпиада школьников по информатике 2010/2011 учебного года. Региональный этап, второй тур, 23 января 2011 г.
URL первоисточника: http://neerc.ifmo.ru/school/archive/2010-2011/ru-olymp-regional-2011-archive.rar
Задачу добавил: alef
Успешно сдано решений: 5
Ограничение по времени: 4 с
Ограничение по памяти 256 Мб
Натуральное число a называется делителем натурального числа b, если b = ac для некоторого натурального числа c. Например, делителями числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно просты, а 18 и 24 — нет.
Будем называть нормальным набор из k чисел (a1, a2, …, ak), если выполнены следующие условия:
1) каждое
из чисел ai является
делителем числа n;
2) выполняется
неравенство a1 < a2 < … < ak;
3) числа
ai и ai+1
для всех i от 1 до k – 1 являются взаимно простыми;
4) произведение
a1a2…ak не превышает n.
Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360.
Требуется написать программу, которая по заданным значениям n и k определяет количество нормальных наборов из k делителей числа n.
Формат входного файла input.txtПервая строка входного файла содержит два целых числа: n и k (2 ≤ n ≤ 108, 2 ≤ k ≤ 10).
Формат выходного файла output.txtВ выходном файле должно содержаться одно число — количество нормальных наборов из k делителей числа n.
Пример входного файла - 190 3Пример выходного файла - 1
16Пример входного файла - 2
10 2Пример выходного файла - 2
4Примечание
Правильные решения для тестов, в которых n ≤ 1000 и k = 2, оцениваются из 30 баллов.
Правильные решения для тестов, в которых k = 2, оцениваются из 60 баллов (в эти баллы включаются также 30 баллов для случая n ≤ 1000, k = 2).