Создайте массив N-длины, имеющий GCD всех его пар, присутствующих в данном 2D-массиве.

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

Примеры:

Input: N = 4, arr[] = {2, 1, 2, 3, 4, 3, 2, 6, 1, 1, 2, 2, 1, 2, 3, 2}
Output: 4, 3, 6, 2
Explanation:
Considering the array A[] as {4, 3, 6, 2}, then the GCD of all possible pairs of this array is given below which is the given array arr[].
{{4, 1, 2, 2},
{1, 3, 3, 1},
{2, 3, 6, 2},
{2, 1, 2, 2}}

Input: N = 1, mat = {100}
Output: 100

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

• Инициализируйте карту, скажем, M сохраните частоту отрицания элемента массива в карте M .
• Инициализируйте переменную, скажем, pos как (N – 1) .
• Теперь для всех элементов массива arr[] найдите максимальный элемент.
• Пройтись по карте М.
• Для каждого элемента исходного массива найдите элемент с максимальной частотой и сохраните его в файле ans.
• Найдите ans[pos] и удалите все GCD от pos+1 до N-1 из ans .
• Обновите pos как pos-1 .
• Повторите вышеуказанные шаги, чтобы найти все элементы исходного массива.
• Наконец, напечатайте ответ .

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

Временная сложность: O(N ² LogN)
Вспомогательное пространство: O(N ² )