MCD, LCM y Propiedad Distributiva

Dados tres enteros x, y, z, la tarea es calcular el valor de MCD(LCM(x,y), LCM(x,z)) . 
Donde, MCD = Máximo Común Divisor, MCM = Mínimo Común Múltiplo
Ejemplos: 
 

Input: x = 15, y = 20, z = 100
Output: 60

Input: x = 30, y = 40, z = 400
Output: 120

Una forma de resolverlo es encontrando MCD(x, y) y usándolo encontramos LCM(x, y). De manera similar, encontramos LCM(x, z) y finalmente encontramos el MCD de los resultados obtenidos.
Se puede hacer un enfoque eficiente por el hecho de que la siguiente versión de la distributividad es cierta:
MCD(MCM (x, y), MCM (x, z)) = MCM(x, MCD(y, z))
Por ejemplo, MCD (MCM(3, 4), MCM(3, 10)) = MCM(3, MCD(4, 10)) = MCM(3, 2) = 6 
Esto reduce nuestro trabajo para calcular el enunciado del problema dado. 
 

// C++ program to compute value of GCD(LCM(x,y), LCM(x,z))
#include<bits/stdc++.h>
using namespace std;
 
// Returns value of  GCD(LCM(x,y), LCM(x,z))
int findValue(int x, int y, int z)
{
    int g = __gcd(y, z);
 
    // Return LCM(x, GCD(y, z))
    return (x*g)/__gcd(x, g);
}
 
int main()
{
    int x = 30, y = 40, z = 400;
    cout << findValue(x, y, z);
    return 0;
}

// Java program to compute value
// of GCD(LCM(x,y), LCM(x,z))
 
class GFG
{
    // Recursive function to
    // return gcd of a and b
    static int __gcd(int a, int b)
    {
        // Everything divides 0
        if (a == 0 || b == 0)
        return 0;
     
        // base case
        if (a == b)
            return a;
     
        // a is greater
        if (a > b)
            return __gcd(a - b, b);
        return __gcd(a, b - a);
    }
     
    // Returns value of GCD(LCM(x,y), LCM(x,z))
    static int findValue(int x, int y, int z)
    {
        int g = __gcd(y, z);
     
        // Return LCM(x, GCD(y, z))
        return (x*g) / __gcd(x, g);
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int x = 30, y = 40, z = 400;
        System.out.print(findValue(x, y, z));
    }
}
 
// This code is contributed by Anant Agarwal.

# Python program to compute
# value of GCD(LCM(x,y), LCM(x,z))
 
# Recursive function to
# return gcd of a and b
def __gcd(a,b):
     
    # Everything divides 0
    if (a == 0 or b == 0):
        return 0
  
    # base case
    if (a == b):
        return a
  
    # a is greater
    if (a > b):
        return __gcd(a-b, b)
    return __gcd(a, b-a)
 
# Returns value of
#  GCD(LCM(x,y), LCM(x,z))
def findValue(x, y, z):
 
    g = __gcd(y, z)
  
    # Return LCM(x, GCD(y, z))
    return (x*g)/__gcd(x, g)
 
# driver code
x = 30
y = 40
z = 400
print("%d"%findValue(x, y, z))
 
# This code is contributed
# by Anant Agarwal.

// C# program to compute value
// of GCD(LCM(x,y), LCM(x,z))
using System;
 
class GFG {
     
    // Recursive function to
    // return gcd of a and b
    static int __gcd(int a, int b)
    {
         
        // Everything divides 0
        if (a == 0 || b == 0)
        return 0;
     
        // base case
        if (a == b)
            return a;
     
        // a is greater
        if (a > b)
            return __gcd(a - b, b);
        return __gcd(a, b - a);
    }
     
    // Returns value of GCD(LCM(x,y),
    // LCM(x,z))
    static int findValue(int x, int y, int z)
    {
        int g = __gcd(y, z);
     
        // Return LCM(x, GCD(y, z))
        return (x*g) / __gcd(x, g);
    }
     
    // Driver code
    public static void Main ()
    {
        int x = 30, y = 40, z = 400;
         
        Console.Write(findValue(x, y, z));
    }
}
 
// This code is contributed by
// Smitha Dinesh Semwal.

<?php
// PHP program to compute value
// of GCD(LCM(x,y), LCM(x,z))
 
// Recursive function to
// return gcd of a and b
function __gcd( $a, $b)
{
     
    // Everything divides 0
    if ($a == 0 or $b == 0)
    return 0;
 
    // base case
    if ($a == $b)
        return $a;
 
    // a is greater
    if ($a > $b)
        return __gcd($a - $b, $b);
    return __gcd($a, $b - $a);
}
 
// Returns value of GCD(LCM(x,y),
// LCM(x,z))
function findValue($x, $y, $z)
{
    $g = __gcd($y, $z);
 
    // Return LCM(x, GCD(y, z))
    return ($x * $g)/__gcd($x, $g);
}
 
    // Driver Code
    $x = 30;
    $y = 40;
    $z = 400;
    echo findValue($x, $y, $z);
 
// This code is contributed by anuj_67.
?>

<script>
// JavaScript program to compute value of GCD(LCM(x,y), LCM(x,z))
function __gcd( a,  b)
    {
        // Everything divides 0
        if (a == 0 || b == 0)
        return 0;
     
        // base case
        if (a == b)
            return a;
     
        // a is greater
        if (a > b)
            return __gcd(a - b, b);
        return __gcd(a, b - a);
    }
// Returns value of  GCD(LCM(x,y), LCM(x,z))
function findValue(x, y, z)
{
    let g = __gcd(y, z);
 
    // Return LCM(x, GCD(y, z))
    return (x*g)/__gcd(x, g);
}
 
    let x = 30, y = 40, z = 400;
    document.write( findValue(x, y, z));
 
// This code contributed by gauravrajput1
 
</script>

Producción: 

120

Complejidad de tiempo: O(log (min(n))) 
Espacio auxiliar: O(log (min(n))) 

Como nota al margen, viceversa también es cierto, es decir, mcd(x, lcm(y, z)) = lcm(gcd(x, y), mcd(x, z)
Referencia:  
https://en.wikipedia. org/wiki/Distributive_property#Other_examples
Este artículo es una contribución de Aarti_Rathi y Mazhar Imam Khan . 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.