Количество массивов размера N, которые могут быть сформированы, начиная с K, так что каждый элемент делится на следующее

Опубликовано: 21 Сентября, 2022

Даны два целых числа 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:

  1. {5, 5, 5}
  2. {5, 5, 1}
  3. {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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ