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