GCD y LCM

¿Qué son GCD y LCM?

• GCD (Greatest Common Divisor / Máximo Común Divisor): el número más grande que divide a ambos sin dejar residuo.
  • GCD(12, 8) = 4 porque 4 divide a 12 y a 8.
• LCM (Least Common Multiple / Mínimo Común Múltiplo): el número más pequeño que es múltiplo de ambos.
  • LCM(4, 6) = 12 porque 12 es el menor número divisible entre 4 y 6.

Analogía: Piensa en dos engranajes. El GCD es cuántos dientes tienen en común. El LCM es cuántas vueltas necesitan para volver a la posición inicial al mismo tiempo.

Algoritmo de Euclides para GCD

La idea genial de Euclides (¡hace 2300 años!): $\gcd(a, b) = \gcd(b, a \mod b)$

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Ejemplo paso a paso

$\gcd(48, 18)$:

• $\gcd(48, 18) = \gcd(18, 48 \mod 18) = \gcd(18, 12)$
• $\gcd(18, 12) = \gcd(12, 18 \mod 12) = \gcd(12, 6)$
• $\gcd(12, 6) = \gcd(6, 12 \mod 6) = \gcd(6, 0)$
• $b = 0$ → respuesta: 6 ✅

Complejidad: $O(\log(\min(a, b)))$ — ¡extremadamente rápido!

Versión recursiva

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

C++ ya lo tiene

#include <algorithm>  // En C++14
// o
#include <numeric>    // En C++17

int g = __gcd(12, 8);    // 4 (funciona en todas las versiones)
int g2 = gcd(12, 8);     // 4 (C++17)

LCM a partir de GCD

La relación mágica:

$\text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;  // Dividir primero para evitar overflow
}

GCD de más de dos números

$\gcd(a, b, c) = \gcd(\gcd(a, b), c)$

int gcdMultiple(vector<int> &v) {
    int resultado = v[0];
    for (int i = 1; i < v.size(); i++) {
        resultado = __gcd(resultado, v[i]);
    }
    return resultado;
}

Lo mismo aplica para LCM:

long long lcmMultiple(vector<int> &v) {
    long long resultado = v[0];
    for (int i = 1; i < v.size(); i++) {
        resultado = lcm(resultado, (long long)v[i]);
    }
    return resultado;
}

GCD extendido

Encuentra $x, y$ tales que $ax + by = \gcd(a, b)$. Útil para inversos modulares.

int gcdExtendido(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int g = gcdExtendido(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

Propiedades útiles

• $\gcd(a, 0) = a$
• $\gcd(a, 1) = 1$
• $\gcd(a, a) = a$
• Si $\gcd(a, b) = 1$, decimos que $a$ y $b$ son coprimos.
• $\gcd(a, b) \times \text{lcm}(a, b) = a \times b$

Ejercicio de práctica

Dados N números, encuentra el GCD y LCM de todos ellos.

Entrada:

4
12 18 24 36

Salida:

GCD: 6
LCM: 72

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

int main() {
    int n;
    cin >> n;
    vector<long long> v(n);
    for (auto &x : v) cin >> x;

    long long g = v[0], l = v[0];
    for (int i = 1; i < n; i++) {
        g = gcd(g, v[i]);
        l = lcm(l, v[i]);
    }

    cout << "GCD: " << g << endl;
    cout << "LCM: " << l << endl;

    return 0;
}