Cuadrados mínimos para cortar uniformemente un rectángulo

Dada una lámina rectangular de largo l y ancho w. necesitamos dividir esta hoja en hojas cuadradas de modo que el número de hojas cuadradas sea el mínimo posible.
Ejemplos:
 

Entrada :l= 4 w=6 
Salida :6 
Podemos formar cuadrados con lado de 1 unidad, pero el número de cuadrados será 24, esto no es mínimo. Si hacemos un cuadrado de lado 2, entonces tenemos 6 cuadrados. y esta es nuestra respuesta requerida. 
Y tampoco podemos hacer cuadrados con el lado 3, si seleccionamos 3 como lado cuadrado, entonces toda la hoja no se puede convertir en cuadrados de igual longitud. 
 

Entrada :l=3 w=5 
Salida :15

La longitud óptima del lado de un cuadrado es igual al MCD de dos números
 

// CPP program to find minimum number of
// squares to make a given rectangle.
#include <bits/stdc++.h>
using namespace std;
 
int countRectangles(int l, int w)
{
    // if we take gcd(l, w), this
    // will be largest possible
    // side for square, hence minimum
    // number of square.
    int squareSide = __gcd(l, w);
 
    // Number of squares.
    return (l * w) / (squareSide * squareSide);
}
 
// Driver code
int main()
{
    int l = 4, w = 6;
    cout << countRectangles(l, w) << endl;
    return 0;
}

// Java program to find minimum number of
// squares to make a given rectangle.
 
class GFG{
static int __gcd(int a, int b) {
   if (b==0) return a;
   return __gcd(b,a%b);
}
static int countRectangles(int l, int w)
{
    // if we take gcd(l, w), this
    // will be largest possible
    // side for square, hence minimum
    // number of square.
    int squareSide = __gcd(l, w);
 
    // Number of squares.
    return (l * w) / (squareSide * squareSide);
}
 
// Driver code
public static void main(String[] args)
{
    int l = 4, w = 6;
    System.out.println(countRectangles(l, w));
}
}
// This code is contributed by mits

# Python3 code to find minimum number of
# squares to make a given rectangle.
 
import math
 
def countRectangles(l, w):
 
    # if we take gcd(l, w), this
    # will be largest possible
    # side for square, hence minimum
    # number of square.
    squareSide = math.gcd(l,w)
     
    # Number of squares.
    return (l*w)/(squareSide*squareSide)
 
# Driver Code
         
if __name__ == '__main__':
    l = 4
    w = 6
    ans = countRectangles(l, w)
    print (int(ans))
 
# this code is contributed by
# SURENDRA_GANGWAR

// C# program to find minimum number of
// squares to make a given rectangle.
 
class GFG{
static int __gcd(int a, int b) {
if (b==0) return a;
return __gcd(b,a%b);
}
static int countRectangles(int l, int w)
{
    // if we take gcd(l, w), this
    // will be largest possible
    // side for square, hence minimum
    // number of square.
    int squareSide = __gcd(l, w);
 
    // Number of squares.
    return (l * w) / (squareSide * squareSide);
}
 
// Driver code
public static void Main()
{
    int l = 4, w = 6;
    System.Console.WriteLine(countRectangles(l, w));
}
}
// This code is contributed by mits

<?php
// PHP program to find minimum number
// of squares to make a given rectangle.
 
function gcd($a, $b)
{
    return $b ? gcd($b, $a % $b) : $a;
}
 
function countRectangles($l, $w)
{
    // if we take gcd(l, w), this
    // will be largest possible
    // side for square, hence minimum
    // number of square.
    $squareSide = gcd($l, $w);
 
    // Number of squares.
    return ($l * $w) / ($squareSide *
                        $squareSide);
}
 
// Driver code
$l = 4;
$w = 6;
echo countRectangles($l, $w) . "\n";
 
// This code is contributed
// by ChitraNayal
?>

<script>
 
// Javascript program to find minimum number of
// squares to make a given rectangle.
 
function __gcd(a, b) {
    if (b==0) return a;
    return __gcd(b,a%b);
}
 
function countRectangles(l, w)
{
    // if we take gcd(l, w), this
    // will be largest possible
    // side for square, hence minimum
    // number of square.
    let squareSide = __gcd(l, w);
 
    // Number of squares.
    return parseInt((l * w) / (squareSide * squareSide));
}
 
// Driver code
    let l = 4, w = 6;
    document.write(countRectangles(l, w));
 
</script>

6

Complejidad de tiempo: O(log(min(a, b))), donde a y b son dos parámetros de gcd.

Espacio auxiliar: O(log(min(a, b)))