Dada una array de enteros arr[] de tamaño N , la tarea es encontrar el GCD de LCM de todos los pares únicos (i, j) de la array, tal que i < j .
Ejemplos:
Entrada: arr[] = {10, 24, 40, 80}
Salida: 40
Explicación:
LCM de todos los pares únicos que siguen las condiciones dadas son:
LCM(10, 24) = 120
LCM(10, 40) = 40
LCM(10, 80) = 80
MCM(24, 40) = 120
MCM(24, 80) = 240
MCM(40, 80) = 80
Por lo tanto, MCD de estos MCM = MCD(120, 40, 80, 120, 240, 80) = 40Entrada: arr[] = {1, 1}
Salida: 1
Enfoque ingenuo: el enfoque más simple es encontrar todos los pares únicos en la array. Luego encuentra su MCM. Luego encuentra el MCD de todos los MCM.
Enfoque eficiente: el enfoque ingenuo anterior se puede optimizar con la ayuda de Suffix array . Podemos usar la array Sufijo para encontrar el MCM de cada elemento emparejado con otros elementos, de manera eficiente. Luego, simplemente podemos encontrar y devolver el GCD de esta array LCM.
- Para cada elemento A[i], necesitamos calcular LCM(a[i], a[j]) , donde j pertenece a [i+1, N-1].
- El MCM de todos los pares donde el elemento inicial es A[i] se puede escribir como
LCM(A[i], MCD(todos los j en el rango i+1 a n-1))
- Para eso construimos una array de sufijos . Digamos sufijo[] que almacena el gcd de elementos que pertenecen al rango [i+1, N-1] .
- Luego cree una array LCM para almacenar el LCM de A[i] y GCD de todos los elementos después de él, es decir
LCM[i] = LCM(A[i], sufijo[i+1])
Donde sufijo[i+1] almacena el MCD de los elementos [i+1, n-1]
- Finalmente, calcule el GCD de todos los elementos en la array LCM.
C++
// C++ code to find the GCD of LCM
// of all unique pairs in an Array
#include <bits/stdc++.h>
using namespace std;
// Find lcm of element x and y
int LCM(int x, int y)
{
return x * y / __gcd(x, y);
}
// Function that finds gcd of lcm
// of all pairs of elements.
void gcd_of_lcm(int n, int arr[])
{
// n is the size of the array.
// arr is the array.
// Suffix array that stores
// the gcd of the array elements.
int suff[n];
// Initialize suffix array.
for(int x = 0; x < n; x++)
{
suff[x] = 1;
}
// Loop that make the suffix gcd array
suff[n - 1] = arr[n - 1];
for(int i = n - 2; i >= 0; i--)
{
suff[i] = __gcd(arr[i], suff[i + 1]);
}
// lcm array that store the lcm
// of ith elements for all j
// that satisfy given condition.
vector<int> lcm;
for(int i = 0; i < n - 1; i++)
{
// we find lcm[i] for lcm
// of ith elements for all j
// using bellow formula.
int y = LCM(arr[i], suff[i + 1]);
// Add lcm of ith elements
// for all j in lcm array.
lcm.push_back(y);
}
// Now we find gcd of all ith elements.
// where i = 0, 1, 2, 3.....n-2.
int ans = lcm[0];
for(int i = 1; i < n - 1; i++)
{
ans = __gcd(ans, lcm[i]);
}
cout << ans << endl;
}
// Driver code
int main()
{
int n = 4;
int a[] = { 10, 24, 40, 80 };
// Function call for input 1
gcd_of_lcm(n, a);
n = 10;
int b[] = { 540, 648, 810, 648, 720,
540, 594, 864, 972, 648 };
// Function call for input 2
gcd_of_lcm(n, b);
}
// This code is contributed by shobhitgupta907
Java
// Java code to find the GCD of LCM
// of all unique pairs in an array
class GFG{
// Function to evaluate GCD of x and y
static int gcd(int x, int y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
// Function that finds gcd of lcm
// of all pairs of elements.
static void gcd_of_lcm(int n, int arr[])
{
// n = size of array i.e. arr[]
// Suffix array that stores
// the GCD of the array elements.
int suff[] = new int[n];
// Initialise the suffix array
for(int i = 0; i < n; i++)
suff[i] = 1;
// Loop that make suffix GCD array
suff[n - 1] = arr[n - 1];
for(int i = n - 2; i >= 0; i--)
suff[i] = gcd(arr[i], suff[i + 1]);
// lcm array that store lcm for pairwise
// consecutive elements
int lcm[] = new int[n - 1];
for(int i = 0; i < n - 1; i++)
// Find LCM using standard known formula
lcm[i] = (arr[i] * suff[i + 1]) /
gcd(arr[i], suff[i + 1]);
// Now we find gcd of all ith elements.
// where i = 0, 1, 2, 3.....n-2.
int ans = lcm[0];
for(int i = 1; i < n - 1; i++)
{
ans = gcd(ans, lcm[i]);
}
// Print the answer
System.out.println(ans);
}
// Driver code
public static void main(String[] args)
{
// 1st input case
int n = 4;
int a[] = { 10, 24, 40, 80 };
// Function call for input 1
gcd_of_lcm(n, a);
// 2nd input case
n = 10;
int b[] = { 540, 648, 810, 648, 720,
540, 594, 864, 972, 648 };
// Function call for input 2
gcd_of_lcm(n, b);
}
}
// This code is contributed by Soumitri Chattopadhyay
Python3
# Python3 code to find the GCD of LCM # of all unique pairs in an Array from math import gcd # find lcm of element x and y def LCM(x, y): return (x * y)//gcd(x, y) # Function that finds gcd of lcm # of all pairs of elements. def gcd_of_lcm(n, arr): # n is the size of the array. # arr is the array. # suffix array that stores # the gcd of the array elements. suff = [1]*n # initialize suffix array. # loop that make the suffix gcd array. suff[n-1] = arr[n-1] for i in range(n-2, -1, -1): suff[i] = gcd(arr[i], suff[i + 1]) # lcm array that store the lcm # of ith elements for all j # that satisfy given condition. lcm = [] for i in range(n-1): # we find lcm[i] for lcm # of ith elements for all j # using bellow formula. y = LCM( arr[i], suff[i + 1]) # add lcm of ith elements # for all j in lcm array. lcm.append(y) # now we find gcd of all ith elements. # where i = 0, 1, 2, 3.....n-2. ans = lcm[0] for i in range(1, n-1): ans = gcd(ans, lcm[i]) print(ans) if __name__== "__main__": n = 4 a =[10, 24, 40, 80] # function call for input 1 gcd_of_lcm(n, a) n = 10 a =[540, 648, 810, 648, 720, 540, 594, 864, 972, 648] # function call for input 2 gcd_of_lcm(n, a)
C#
// C# code to find the GCD of LCM
// of all unique pairs in an array
using System;
class GFG{
// Function to evaluate GCD of x and y
static int gcd(int x, int y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
// Function that finds gcd of lcm
// of all pairs of elements.
static void gcd_of_lcm(int n, int[] arr)
{
// n = size of array i.e. arr[]
// Suffix array that stores
// the GCD of the array elements.
int[] suff = new int[n];
// Initialise the suffix array
for(int i = 0; i < n; i++)
suff[i] = 1;
// Loop that make suffix GCD array
suff[n - 1] = arr[n - 1];
for(int i = n - 2; i >= 0; i--)
suff[i] = gcd(arr[i], suff[i + 1]);
// lcm array that store lcm for pairwise
// consecutive elements
int[] lcm = new int[n - 1];
for(int i = 0; i < n - 1; i++)
// Find LCM using standard known formula
lcm[i] = (arr[i] * suff[i + 1]) /
gcd(arr[i], suff[i + 1]);
// Now we find gcd of all ith elements.
// where i = 0, 1, 2, 3.....n-2.
int ans = lcm[0];
for(int i = 1; i < n - 1; i++)
{
ans = gcd(ans, lcm[i]);
}
// Print the answer
Console.WriteLine(ans);
}
// Driver code
public static void Main()
{
// 1st input case
int n = 4;
int[] a = { 10, 24, 40, 80 };
// Function call for input 1
gcd_of_lcm(n, a);
// 2nd input case
n = 10;
int[] b = { 540, 648, 810, 648, 720,
540, 594, 864, 972, 648 };
// Function call for input 2
gcd_of_lcm(n, b);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript code to find the GCD of LCM
// of all unique pairs in an array
// Function to evaluate GCD of x and y
function gcd(x, y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
// Function that finds gcd of lcm
// of all pairs of elements.
function gcd_of_lcm(n, arr)
{
// n = size of array i.e. arr[]
// Suffix array that stores
// the GCD of the array elements.
let suff = new Array(n);
// Initialise the suffix array
for(let i = 0; i < n; i++)
suff[i] = 1;
// Loop that make suffix GCD array
suff[n - 1] = arr[n - 1];
for(let i = n - 2; i >= 0; i--)
suff[i] = gcd(arr[i], suff[i + 1]);
// lcm array that store lcm for pairwise
// consecutive elements
let lcm = new Array(n - 1);
for(let i = 0; i < n - 1; i++)
// Find LCM using standard known formula
lcm[i] = parseInt((arr[i] * suff[i + 1]) /
gcd(arr[i], suff[i + 1]), 10);
// Now we find gcd of all ith elements.
// where i = 0, 1, 2, 3.....n-2.
let ans = lcm[0];
for(let i = 1; i < n - 1; i++)
{
ans = gcd(ans, lcm[i]);
}
// Print the answer
document.write(ans + "</br>");
}
// Driver code
// 1st input case
let n = 4;
let a = [ 10, 24, 40, 80 ];
// Function call for input 1
gcd_of_lcm(n, a);
// 2nd input case
n = 10;
let b = [ 540, 648, 810, 648, 720,
540, 594, 864, 972, 648 ];
// Function call for input 2
gcd_of_lcm(n, b);
// This code is contributed by rameshtravel07
</script>
Producción:
40 54
Complejidad de tiempo: O(N * log M) , donde M es el elemento máximo en la array.
Complejidad espacial: O(N)
Publicación traducida automáticamente
Artículo escrito por ghoshashis545 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA