Количество различных GCD среди всех непустых подпоследовательностей данного массива

Учитывая целочисленный массив arr[] размера N , задача состоит в том, чтобы вычислить общее количество различных наибольших общих делителей (GCD) среди всех непустых подпоследовательностей arr[] .

Примеры:

Input: arr[]={3,4,8} N=3
Output:
4
Explanation:
The different non-empty subsequences possible are {3}, {4}, {8}, {3,4}, {4,8}, {3,8}, {3,4,8} and their corresponding GCDs are 3,4,8,1,4,1,1. 
Thus, the total number of distinct GCDs is 4 (1,3,4,8).

Input: arr[]={3,11,14,6,12}, N=5
Output:
7

Наивный подход . Наивный подход состоит в том, чтобы найти все подпоследовательности, вычислить GCD для каждой из них и, наконец, вычислить общее количество различных GCD .

Временная сложность: O(2 ^N .Log(M)), где M — самый большой элемент в массиве.

Подход: Данная проблема может быть решена на основе следующих наблюдений:

1. Максимально возможный GCD не может превышать самый большой элемент массива (скажем, M ). Следовательно, все возможные НОД лежат в диапазоне от 1 до M .
2. Перебирая все возможные значения НОД , то есть от 1 до M , и проверяя, есть ли какие-либо кратные i , которые присутствуют в массиве и имеют НОД , равный i , проблема может быть решена.

Выполните следующие шаги, чтобы решить проблему:

1. Инициализировать переменную в 0.
2. Вычислите и сохраните максимальное количество элементов в переменной, скажем, M .
3. Храните все элементы arr в карте Mp для постоянного доступа.
4. Переберите все возможные значения НОД , т. е. от 1 до M , используя переменную i , и выполните следующие действия:
   • Переберите кратные M , представленные в arr , используя переменную j , и сделайте следующее:
   • Если GCD становится i в какой-то момент, увеличьте an и прервите.

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

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