Encuentre GCD de cada elemento de la array B[] agregado a todos los elementos de la array A[]

Dadas dos arrays a[] y b[] de longitud n y m respectivamente, la tarea es encontrar el máximo común divisor (MCD) de {a[0] + b[i], a[1] + b[i], a[2] + b[i], …, a[n – 1] + b[i]} (donde 0 <= i <= m – 1).

Entrada: a[] = {1, 10, 22, 64}, b[] = {5, 23, 14, 13}
Salida: 3 3 3 1  
Explicación:

• i = 1:  MCD(5+1, 5+10, 5+22, 5+64) = MCD(6, 15, 27, 69) = 3
• i = 2 : MCD(23+1, 23+10, 23+22, 23+64) = MCD(24, 33, 45, 87) = 3
• i = 3 : MCD(14+1, 14+10, 14+22, 14+64) = MCD(15, 24, 36, 78) = 3
• i = 4 : MCD(13+1, 13+10, 13+22, 13+64) = MCD(14, 23, 35, 77) = 1

Entrada: a[] = {12, 30}, b[] = {5, 23, 14, 13}
Salida: 1 1 2 1

Enfoque: el problema se puede resolver de manera eficiente utilizando la propiedad del algoritmo GCD euclidiano que establece GCD (x, y) = GCD (x−y, y) . Lo mismo se aplica a los argumentos múltiples GCD(x, y, z, …) = GCD(x−y. y, z, …) . Aplicando esta propiedad, el problema se puede resolver siguiendo los pasos que se detallan a continuación:

• Para calcular GCD(a[0] + b[i], …, a[n – 1] + b[i]) , reste a[0] + b[i] de todos los demás argumentos.
• Ahora, MCD ( a[0] + b[i], …, a[n – 1] + b[i]) = MCD ( a[0] + b[i], a[1] − a[0] , …, un[n – 1] − un[0]) .
• Encuentre G = GCD(a[1] − a[0], …, a[n – 1] − a[0]) , entonces mcd para cualquier i se puede calcular como MCD(a[0] + b[i ], G) .
• Iterar sobre todos los valores posibles de i de 1 a m y calcular gcd como G(i) = GCD(a[1]+b[i], G) e imprimir G(i).

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
// Function to calculate gcd for every i
void findGCDs(vector<ll> a, vector<ll> b)
{
    ll g = 0;
 
    int n = a.size();
    int m = b.size();
 
    // Update GCD of a[1] - a[0],
    // a[2] - a[0], .... a[n - 1] - a[0]
    for (int i = 1; i < n; i++) {
 
        g = __gcd(g, a[i] - a[0]);
    }
 
    // Print gcd(g, a[0] + b[j])
    for (int j = 0; j < m; j++) {
 
        cout << __gcd(g, a[0] + b[j]) << " ";
    }
}
 
// Driver Code
int main()
{
    // Given Input
    vector<ll> a = { 1, 10, 22, 64 },
               b = { 5, 23, 14, 13 };
 
    // Function Call
    findGCDs(a, b);
 
    return 0;
}

// Java code for the above approach
public class GFG{
    static int gcd(int a, int b)
    {    
       if (b == 0)
          return a;
       return gcd(b, a % b);
    }
     
    // Function to calculate gcd for every i
    static void findGCDs(int[] a, int[] b)
    {
        int g = 0;
     
        int n = a.length;
        int m = b.length;
     
        // Update GCD of a[1] - a[0],
        // a[2] - a[0], .... a[n - 1] - a[0]
        for (int i = 1; i < n; i++) {
     
            g = gcd(g, a[i] - a[0]);
        }
     
        // Print gcd(g, a[0] + b[j])
        for (int j = 0; j < m; j++) {
     
            System.out.print(gcd(g, a[0] + b[j]) + " ");
        }
    }
     
    // Driver Code
public static void main(String args[])
   {
       
    // Given Input
    int[] a = { 1, 10, 22, 64 },
        b = { 5, 23, 14, 13 };
 
    // Function Call
    findGCDs(a, b);
   }
}
 
// This code is contributed by SoumikMondal.

# Python program for above approach
import math
 
# Function to calculate gcd for every i
def findGCDs( a,  b):
    g = 0
    n = len(a)
    m = len(b)
     
    # Update GCD of a[1] - a[0],
    # a[2] - a[0], .... a[n - 1] - a[0]
    for i in range(1,n):
        g = math.gcd(g, a[i] - a[0])
     
    # Pr gcd(g, a[0] + b[j])
    for j in range(m):
        print(math.gcd(g, a[0] + b[j]), end=" ")
     
# Driver Code
 
# Given Input
a = [1, 10, 22, 64]
b = [5, 23, 14, 13]
 
# Function Call
findGCDs(a, b)
 
#This code is contributed by shubhamsingh10

//C# code for the above approach
using System;
 
public class GFG{
    static int gcd(int a, int b)
    {    
       if (b == 0)
          return a;
       return gcd(b, a % b);
    }
     
    // Function to calculate gcd for every i
    static void findGCDs(int[] a, int[] b)
    {
        int g = 0;
     
        int n = a.Length;
        int m = b.Length;
     
        // Update GCD of a[1] - a[0],
        // a[2] - a[0], .... a[n - 1] - a[0]
        for (int i = 1; i < n; i++) {
     
            g = gcd(g, a[i] - a[0]);
        }
     
        // Print gcd(g, a[0] + b[j])
        for (int j = 0; j < m; j++) {
     
            Console.Write(gcd(g, a[0] + b[j]) + " ");
        }
    }
     
    // Driver Code
    static public void Main ()
   {
       
    // Given Input
    int[] a = { 1, 10, 22, 64 },
        b = { 5, 23, 14, 13 };
 
    // Function Call
    findGCDs(a, b);
   }
}
 
// This code is contributed by shubhamsingh10.

<script>
    // JavaScript Program for the above approach
 
    // Function to calculate gcd for every i
    function gcd(a, b)
    {
     
        // Everything divides 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;
 
        // base case
        if (a == b)
            return a;
 
        // a is greater
        if (a > b)
            return gcd(a - b, b);
        return gcd(a, b - a);
    }
    function findGCDs(a, b) {
        let g = 0;
 
        let n = a.length;
        let m = b.length;
 
        // Update GCD of a[1] - a[0],
        // a[2] - a[0], .... a[n - 1] - a[0]
        for (let i = 1; i < n; i++) {
 
            g = gcd(g, a[i] - a[0]);
        }
 
        // Print gcd(g, a[0] + b[j])
        for (let j = 0; j < m; j++) {
 
            document.write(gcd(g, a[0] + b[j]) + " ");
        }
    }
 
    // Driver Code
 
    // Given Input
    let a = [1, 10, 22, 64]
    let b = [5, 23, 14, 13];
 
    // Function Call
    findGCDs(a, b);
 
// This code is contributed by Potta Lokesh
</script>

3 3 3 1

Complejidad de tiempo: O((N + M) * log(X)), donde M es el elemento máximo en la array a[] .
Espacio Auxiliar: O(1)