Medio · Algoritmos
Máximo común divisor
Lee dos enteros positivos e imprime su MCD. El camino ingenuo (probar divisores) pasa; el de Euclides (2.300 años) es el primer algoritmo de verdad inteligente que escribe casi todo el mundo.
En una fraseAlgoritmo de Euclides: mientras b no sea 0, sustituye (a, b) por (b, a % b); la respuesta es a, y necesita O(log min(a, b)) pasos incluso con 10⁹.
El problema
Entrada: una línea con dos enteros positivos a y b (1 ≤ a, b ≤ 10⁹).
Salida: su máximo común divisor.
Ejemplos:
| Entrada | Salida |
|---|---|
12 18 | 6 |
7 13 | 1 |
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — la identidad clave
Todo número que divide a a y a b también divide a a % b — así que gcd(a, b) = gcd(b, a % b). Cada paso encoge los números, y como a % b siempre es menor que b, converge rapidísimo.
Pista 2 — la forma del bucle
while (b != 0) { int t = a % b; a = b; b = t; } — hace falta la temporal t porque sobrescribir a primero destruiría el valor que iba a parar en b. (Es el mismo baile de tres líneas del intercambio con punteros.) Cuando b llega a 0, a tiene la respuesta.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
cout << a << endl;
return 0;
}Por qué aplasta al método ingenuo: con entradas de hasta mil millones, probar divisores son hasta mil millones de vueltas; Euclides tarda como máximo ~45 (el peor caso son Fibonacci consecutivos — mira el problema siguiente). Traza gcd(12, 18) a mano: (12,18) → (18,12) → (12,6) → (6,0) → respuesta 6. Cuando haga clic, el mcm está a una línea: a * b / gcd.
Análisis profundo
Por qué funciona
La identidad de Euclides — gcd(a,b) = gcd(b, a % b) — es el algoritmo no trivial más antiguo que aún se usa a diario, y el modelo de «encoger el problema en cada paso».
El coste
O(log min(a,b)). Dos Fibonacci consecutivos son el peor caso.
Dónde falla
while (b > 0)falla con entradas negativas; normaliza con abs primero.- Probar todos los divisores desde min(a,b) hacia abajo es O(n) y se agota con parejas grandes y coprimas.
Siguiente paso
Recursión que encoge igual: Fibonacci.
Dos cosas para recordar
- gcd(a,b) = gcd(b, a % b).
- Es O(log n), no O(n): el bucle ingenuo es mil veces más lento.
🐞 Esta versión falla: ábrela y pruébala
Imprime b, que al final del bucle vale 0
#include <iostream>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
while (b > 0) {
int t = a % b;
a = b;
b = t;
}
cout << b << endl;
return 0;
}