Количество массивов размера N, которые могут быть сформированы, начиная с K, так что каждый элемент делится на следующее
Даны два целых числа N и K , задача состоит в том, чтобы найти количество различных массивов размера N , которые могут быть сформированы с первым элементом как K таким образом, что каждый элемент, кроме последнего, делится на следующий элемент в массиве. Поскольку число может быть очень большим, выведите модуль 10 9 + 7 .
Примеры:
Input: N = 3, K = 5
Output: 3
Explanation:
There are 3 possible valid array starting with value 5 satisfying the given criteria:
- {5, 5, 5}
- {5, 5, 1}
- {5, 1, 1}.
Therefore the total count is 3.
Input: N = 3, K = 6
Output: 9
Подход: Данная проблема может быть решена с использованием теории чисел и комбинаторики. Первым элементом массива является K , затем следующий элемент массива является одним из множителей K . Выполните следующие шаги, чтобы решить данную проблему:
- Инициализируйте переменную, скажем, res как 1 , которая хранит результирующее количество сформированных массивов.
- Найдите все степени простых множителей числа K и для каждого простого множителя P выполните следующие действия:
- Найдите, сколько раз P встречается в значении K . Пусть этот счет будет счетом .
- Количество возможных способов сохранить один из факторов P определяется как (N - count + 1) C count .
- Умножьте значение (N – count + 1) C count на значение res .
- После выполнения вышеуказанных шагов выведите в качестве результата значение res .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(sqrt(N))
Вспомогательное пространство: O(1)