Dada una array de n números y también se dan varias consultas. Cada consulta estará representada por dos números enteros l, r. La tarea es encontrar el GCD de todos los números de la array excluyendo los números dados en el rango l, r (ambos inclusive) para cada consulta.
Ejemplos:
Input : arr[] = {2, 6, 9} Ranges [0 0], [1 1], [1 2] Output : 3 1 2 GCD of numbers excluding [0 0] or first element is GCD(6, 9) = 3 GCD of numbers excluding the [1 1] or second element is GCD(2, 9) = 1 GCD of numbers excluding [1 2] is equal to first element = 2
Nota: Usamos una indexación basada en 1 en la explicación a continuación
. Comenzamos con la pregunta muy básica de cómo calcular el MCD de dos números. La mejor opción es el algoritmo de Euclides . Ahora, cómo calcular el MCD de más de un número, la solución es simple suponiendo que hay tres números a, b y c. MCD(a, b, c) = MCD(MCD(a, b), c). De esta manera, podemos encontrar fácilmente el MCD de cualquier cantidad de números.
Una forma simple de resolver la pregunta para cada consulta suponga que el rango dado es l y r. Tome GCD de los números de 1 a l-1, suponga que es x, luego tome GCD de los números del rango r + 1 a n, sea y, la salida de cada consulta será GCD (x, y).
Una solución eficientees usar dos arrays, una como array de prefijos y la segunda como array de sufijos. El i-ésimo índice de la array de prefijos almacenará el GCD de los números del 1 al i y el i-ésimo índice de la array de sufijos denotará el GCD de los números de la i a la n. Ahora supongamos que en un rango de consulta particular dado es l, r, es obvio que la salida para esa consulta será GCD (prefijo [l-1], sufijo [r + 1]).
C++
// C++ program for queries of GCD excluding // given range of elements. #include<bits/stdc++.h> using namespace std; // Filling the prefix and suffix array void FillPrefixSuffix(int prefix[], int arr[], int suffix[], int n) { // Filling the prefix array following relation // prefix(i) = __gcd(prefix(i-1), arr(i)) prefix[0] = arr[0]; for (int i=1 ;i<n; i++) prefix[i] = __gcd(prefix[i-1], arr[i]); // Filling the suffix array following the // relation suffix(i) = __gcd(suffix(i+1), arr(i)) suffix[n-1] = arr[n-1]; for (int i=n-2; i>=0 ;i--) suffix[i] = __gcd(suffix[i+1], arr[i]); } // To calculate gcd of the numbers outside range int GCDoutsideRange(int l, int r, int prefix[], int suffix[], int n) { // If l=0, we need to tell GCD of numbers // from r+1 to n if (l==0) return suffix[r+1]; // If r=n-1 we need to return the gcd of // numbers from 1 to l if (r==n-1) return prefix[l-1]; return __gcd(prefix[l-1], suffix[r+1]); } // Driver function int main() { int arr[] = {2, 6, 9}; int n = sizeof(arr)/sizeof(arr[0]); int prefix[n], suffix[n]; FillPrefixSuffix(prefix, arr, suffix, n); int l = 0, r = 0; cout << GCDoutsideRange(l, r, prefix, suffix, n) << endl; l = 1 ; r = 1; cout << GCDoutsideRange(l, r, prefix, suffix, n) << endl; l = 1 ; r = 2; cout << GCDoutsideRange(l, r, prefix, suffix, n) << endl; return 0; }
Java
// Java program for queries of GCD excluding // given range of elements. import java.util.*; class GFG { // Calculating GCD using euclid algorithm static int GCD(int a, int b) { if (b == 0) return a; return GCD(b, a % b); } // Filling the prefix and suffix array static void FillPrefixSuffix(int prefix[], int arr[], int suffix[], int n) { // Filling the prefix array following relation // prefix(i) = GCD(prefix(i-1), arr(i)) prefix[0] = arr[0]; for (int i = 1; i < n; i++) prefix[i] = GCD(prefix[i - 1], arr[i]); // Filling the suffix array following the // relation suffix(i) = GCD(suffix(i+1), arr(i)) suffix[n - 1] = arr[n - 1]; for (int i = n - 2; i >= 0; i--) suffix[i] = GCD(suffix[i + 1], arr[i]); } // To calculate gcd of the numbers outside range static int GCDoutsideRange(int l, int r, int prefix[], int suffix[], int n) { // If l=0, we need to tell GCD of numbers // from r+1 to n if (l == 0) return suffix[r + 1]; // If r=n-1 we need to return the gcd of // numbers from 1 to l if (r == n - 1) return prefix[l - 1]; return GCD(prefix[l - 1], suffix[r + 1]); } // Driver code public static void main(String[] args) { int arr[] = {2, 6, 9}; int n = arr.length; int prefix[] = new int[n]; int suffix[] = new int[n]; FillPrefixSuffix(prefix, arr, suffix, n); int l = 0, r = 0; System.out.println(GCDoutsideRange (l, r, prefix, suffix, n)); l = 1; r = 1; System.out.println(GCDoutsideRange (l, r, prefix, suffix, n)); l = 1; r = 2; System.out.println(GCDoutsideRange (l, r, prefix, suffix, n)); } } // This code is contributed by Anant Agarwal.
Python3
# Python program for # queries of GCD excluding # given range of elements. # Calculating GCD # using euclid algorithm def GCD(a,b): if (b==0): return a return GCD (b, a%b) # Filling the prefix # and suffix array def FillPrefixSuffix(prefix,arr,suffix,n): # Filling the prefix array # following relation # prefix(i) = GCD(prefix(i-1), arr(i)) prefix[0] = arr[0] for i in range(1,n): prefix[i] = GCD (prefix[i-1], arr[i]) # Filling the suffix # array following the # relation suffix(i) = GCD(suffix(i+1), arr(i)) suffix[n-1] = arr[n-1] for i in range(n-2,-1,-1): suffix[i] = GCD (suffix[i+1], arr[i]) # To calculate gcd of # the numbers outside range def GCDoutsideRange(l,r,prefix,suffix,n): # If l=0, we need to tell GCD of numbers # from r+1 to n if (l==0): return suffix[r+1] # If r=n-1 we need to return the gcd of # numbers from 1 to l if (r==n-1): return prefix[l-1] return GCD(prefix[l-1], suffix[r+1]) # Driver code arr = [2, 6, 9] n = len(arr) prefix=[] suffix=[] for i in range(n+1): prefix.append(0) suffix.append(0) FillPrefixSuffix(prefix, arr, suffix, n) l = 0 r = 0 print(GCDoutsideRange(l, r, prefix, suffix, n)) l = 1 r = 1 print(GCDoutsideRange(l, r, prefix, suffix, n)) l = 1 r = 2 print(GCDoutsideRange(l, r, prefix, suffix, n)) # This code is contributed # by Anant Agarwal.
C#
// C# program for queries of GCD // excluding given range of elements. using System; class GFG { // Calculating GCD using // euclid algorithm static int GCD(int a, int b) { if (b == 0) return a; return GCD(b, a % b); } // Filling the prefix and suffix array static void FillPrefixSuffix(int []prefix, int []arr, int []suffix, int n) { // Filling the prefix array following // relation prefix(i) = // GCD(prefix(i - 1), arr(i)) prefix[0] = arr[0]; for (int i = 1; i < n; i++) prefix[i] = GCD(prefix[i - 1], arr[i]); // Filling the suffix array following // the relation suffix(i) = // GCD(suffix(i+1), arr(i)) suffix[n - 1] = arr[n - 1]; for (int i = n - 2; i >= 0; i--) suffix[i] = GCD(suffix[i + 1], arr[i]); } // To calculate gcd of the numbers outside range static int GCDoutsideRange(int l, int r, int []prefix, int []suffix, int n) { // If l=0, we need to tell // GCD of numbers from r+1 to n if (l == 0) return suffix[r + 1]; // If r=n-1 we need to return the // gcd of numbers from 1 to l if (r == n - 1) return prefix[l - 1]; return GCD(prefix[l - 1], suffix[r + 1]); } // Driver Code public static void Main() { int []arr = {2, 6, 9}; int n = arr.Length; int []prefix = new int[n]; int []suffix = new int[n]; FillPrefixSuffix(prefix, arr, suffix, n); int l = 0, r = 0; Console.WriteLine(GCDoutsideRange (l, r, prefix, suffix, n)); l = 1; r = 1; Console.WriteLine(GCDoutsideRange (l, r, prefix, suffix, n)); l = 1; r = 2; Console.Write(GCDoutsideRange (l, r, prefix, suffix, n)); } } // This code is contributed by Nitin Mittal.
PHP
<?php // PHP program for queries of GCD excluding // given range of elements. // Calculating GCD using euclid algorithm function GCD($a, $b) { if ($b == 0) return $a; return GCD ($b, $a % $b); } // Filling the prefix and suffix array function FillPrefixSuffix(&$prefix, &$arr, &$suffix, $n) { // Filling the prefix array following relation // prefix(i) = GCD(prefix(i-1), arr(i)) $prefix[0] = $arr[0]; for ($i = 1; $i < $n; $i++) $prefix[$i] = GCD ($prefix[$i - 1], $arr[$i]); // Filling the suffix array following the // relation suffix(i) = GCD(suffix(i+1), arr(i)) $suffix[$n - 1] = $arr[$n - 1]; for ($i = $n - 2; $i >= 0 ;$i--) $suffix[$i] = GCD ($suffix[$i + 1], $arr[$i]); } // To calculate gcd of the numbers outside range function GCDoutsideRange($l, $r, &$prefix, &$suffix, $n) { // If l=0, we need to tell GCD of numbers // from r+1 to n if ($l == 0) return $suffix[$r + 1]; // If r=n-1 we need to return the gcd of // numbers from 1 to l if ($r == $n - 1) return $prefix[$l - 1]; return GCD($prefix[$l - 1], $suffix[$r + 1]); } // Driver Code $arr = array(2, 6, 9); $n = sizeof($arr); $prefix = array_fill(0, $n, NULL); $suffix = array_fill(0, $n, NULL); FillPrefixSuffix($prefix, $arr, $suffix, $n); $l = 0; $r = 0; echo GCDoutsideRange($l, $r, $prefix, $suffix, $n) . "\n"; $l = 1 ; $r = 1; echo GCDoutsideRange($l, $r, $prefix, $suffix, $n) . "\n"; $l = 1 ; $r = 2; echo GCDoutsideRange($l, $r, $prefix, $suffix, $n) . "\n"; // This code is contributed by ita_c ?>
Javascript
<script> // JavaScript program for queries of GCD excluding // given range of elements. // Calculating GCD using euclid algorithm function GCD(a , b) { if (b == 0) return a; return GCD(b, a % b); } // Filling the prefix and suffix array function FillPrefixSuffix(prefix , arr , suffix , n) { // Filling the prefix array following relation // prefix(i) = GCD(prefix(i-1), arr(i)) prefix[0] = arr[0]; for (i = 1; i < n; i++) prefix[i] = GCD(prefix[i - 1], arr[i]); // Filling the suffix array following the // relation suffix(i) = GCD(suffix(i+1), arr(i)) suffix[n - 1] = arr[n - 1]; for (i = n - 2; i >= 0; i--) suffix[i] = GCD(suffix[i + 1], arr[i]); } // To calculate gcd of the numbers outside range function GCDoutsideRange(l , r , prefix , suffix , n) { // If l=0, we need to tell GCD of numbers // from r+1 to n if (l == 0) return suffix[r + 1]; // If r=n-1 we need to return the gcd of // numbers from 1 to l if (r == n - 1) return prefix[l - 1]; return GCD(prefix[l - 1], suffix[r + 1]); } // Driver code var arr = [ 2, 6, 9 ]; var n = arr.length; var prefix = Array(n).fill(0); var suffix = Array(n).fill(0); FillPrefixSuffix(prefix, arr, suffix, n); var l = 0, r = 0; document.write(GCDoutsideRange(l, r, prefix, suffix, n)); document.write("<br>"); l = 1; r = 1; document.write(GCDoutsideRange(l, r, prefix, suffix, n)); document.write("<br>"); l = 1; r = 2; document.write(GCDoutsideRange(l, r, prefix, suffix, n)); document.write("<br>"); // This code is contributed by todaysgaurav </script>
Producción:
3 1 2
Complejidad temporal: O(nlogn)
Espacio auxiliar: O(n)
Este artículo es una contribución de Ayush Jha . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA