Подсчет подпоследовательностей с НОД, равным X

Дан массив arr[] , состоящий из N целых чисел и положительного целого числа X , задача состоит в том, чтобы подсчитать подпоследовательности с НОД ровно X .

Примеры:

Input: arr[] = {6, 4, 30}  X = 2
Output: 3
Explanation: Subsequences with GCD(=2) are { {6, 4, 30}, {4, 30}, {6, 4} }. Hence, 3 is the answer.

Input: arr[] = {6, 6, 6}  X = 3
Output: 0
 

Подход: Данную проблему можно решить с помощью динамического программирования. Выполните следующие шаги, чтобы решить данную проблему.

• Определите двумерную таблицу dp dp[i][j] , которая будет обозначать количество допустимых подпоследовательностей до индекса i с GCD(= j ).
• Для каждой итерации у нас есть 2 варианта:
  • Возьмем текущий элемент: таблицу dp можно обновить как dp[i + 1][gcd(j, arr[i])] += dp[i][j] .
  • Пропустить текущий элемент: таблица dp может быть обновлена как dp[i+1][j] += dp[i][j] .
• Базовый случай: dp[0][0] = 1 .
• Поскольку НОД двух чисел никогда не может быть больше двух чисел, поэтому значения j будут равны максимальному элементу в массиве. Следовательно, его можно решить итеративно, и окончательный ответ будет dp[N][X] .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*M), где M — максимальный элемент массива .
Вспомогательное пространство: O(N*M)