Genere una array de longitud N que tenga GCD de todos sus pares presentes en una array 2D dada

Dada una array 2D arr[][] que consta de N*N enteros positivos, la tarea es generar una array de N longitud tal que el Máximo Común Divisor (GCD) de todos los pares posibles de esa array esté presente en la array arr[] [] .

Ejemplos:

Entrada: N = 4, arr[] = {2, 1, 2, 3, 4, 3, 2, 6, 1, 1, 2, 2, 1, 2, 3, 2}
Salida: 4, 3, 6 , 2
Explicación:
considerando el arreglo A[] como {4, 3, 6, 2}, entonces el MCD de todos los pares posibles de este arreglo se da a continuación, que es el arreglo dado arr[].
{{4, 1, 2, 2},
{1, 3, 3, 1},
{2, 3, 6, 2},
{2, 1, 2, 2}}

Entrada: N = 1, mat = {100}
Salida: 100

Enfoque: el problema anterior se puede resolver usando el hecho de que el GCD del elemento más grande en la array original consigo mismo es el más grande en el arr[] y después de eliminar los pares de gcd con ese elemento, se puede encontrar el siguiente elemento. Siga los pasos a continuación para resolver el problema dado:

• Inicialice un mapa , digamos, M almacene la frecuencia de negación del elemento de array en el mapa M.
• Inicialice una variable, digamos pos como (N – 1) .
• Ahora, para todos los elementos de la array arr[] encuentre el elemento máximo.
• Recorrer el mapa M.
• Para cada elemento de la array original, encuentre el elemento con la frecuencia máxima y guárdelo en el ans.
• Encuentre ans[pos] y elimine todos los GCD de pos+1 a N-1 de ans .
• Actualice pos como pos-1 .
• Repita los pasos anteriores para encontrar todos los elementos de la array original.
• Finalmente, imprima el ans .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int n;
  
// Function to calculate GCD of two numbers
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
  
// Function to generate an N-length
// array having GCD of all pairs
// present in the array mat[][]
void restoreArray(vector<int> mat)
{
    map<int, int> cnt;
  
    // Stores the required array
    vector<int> ans(n);
  
    for (int i = 0; i < (n * n); ++i) {
  
        // Store frequencies in map
        // in decreasing order
        cnt[-mat[i]]++;
    }
  
    int pos = n - 1;
  
    for (auto it = cnt.begin();
         it != cnt.end(); ++it) {
  
        int x = -it->first;
        while (it->second) {
  
            // gcd(x, x)
            ans[pos] = x;
            --it->second;
  
            // Remove all GCDs for
            // indices pos + 1 -> n - 1
            for (int i = pos + 1; i < n; ++i)
  
                cnt[-gcd(ans[pos], ans[i])] -= 2;
  
            // Decreasing pos
            pos--;
        }
    }
  
    // Print restored array
    for (int i = 0; i < n; ++i)
        printf("%d ", ans[i]);
}
  
// Driver Code
int main()
{
  
    // Given Input
    n = 4;
    vector<int> mat{ 2, 1, 2, 3, 4, 3,
                     2, 6, 1, 1, 2,
                     2, 1, 2, 3, 2 };
  
    // Function Call
    restoreArray(mat);
    return 0;
}

2 3 4 6

Complejidad de Tiempo: O(N ² LogN)
Espacio Auxiliar: O(N ² )