Consultas de GCD de todos los números de una array excepto los elementos en un rango dado

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++ 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 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.

# 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# 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 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
?>

<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.