Euclides extendido (gcd)

Tema: Matemática y Combinatoria · temarios: Syllabus OCI · Syllabus IOI

📍 Ampliación: parte de divisibilidad y MCD del módulo 10. Esta técnica se desarrolla en la ficha, no en esa clase.

Qué hace

Calcula gcd(a, b) y además coeficientes x, y tales que a·x + b·y = gcd(a, b).

Complejidad: O(log min(a, b)).

Cuándo usarlo

Cuando necesitas resolver ax + by = c en enteros — por ejemplo, ‘¿puedo pagar exactamente c con monedas de a y b?’. Si solo quieres el máximo común divisor, std::gcd(a, b) basta (módulo 10 de la Ruta de Aprendizaje). Es material de nivel avanzado: el inverso modular por esta vía está fuera del syllabus, ver Syllabus IOI.

Implementación recomendada (C++)

// Devuelve g = gcd(a, b) y deja x, y con a*x + b*y = g.
long long ext_gcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

⚠️ Notas

Para solo el gcd, usa std::gcd (C++17, en ). El gcd básico SÍ entra en el syllabus; el inverso modular NO.