Edición didáctica en español. El código y sus salidas conservan el original.

Funciones recursivas: MCD y MCM de un array

Combina el algoritmo de Euclides con parámetros de salida mediante punteros.

Lee K enteros positivos. Implementa gcd(a, b) de forma recursiva con gcd(b, a % b) y el caso base b == 0. Calcula el mínimo común múltiplo con (a / gcd(a, b)) * b.

Implementa find_array_gcd_lcm con los parámetros k, arr, out_gcd y out_lcm. Recorre el array acumulando ambos resultados y escríbelos mediante los punteros de salida. Imprime las etiquetas Array GCD: y Array LCM: sin traducirlas.

Entrada

Primera línea: K. Segunda línea: K enteros positivos separados por espacios.

Salida

Array GCD: <mcd> | Array LCM: <mcm>

Restricciones

2 <= K <= 10
1 <= arr[i] <= 1.000.000
El MCM final cabe en un long long con signo de 64 bits.

Pistas

Cuando b == 0, devuelve a; en otro caso llama a gcd(b, a % b).
Divide antes de multiplicar al calcular el MCM.

Código C

#include <stdio.h>

// Recursive Euclidean algorithm
long long gcd(long long a, long long b) {
    // TODO: Base case and recursive call
    return 0;
}

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

// Function modifying outputs via pointers
void find_array_gcd_lcm(int k, long long arr[], long long *out_gcd, long long *out_lcm) {
    // TODO: Loop through array and accumulate overall GCD and LCM
}

int main(void) {
    int k;
    if (scanf("%d", &k) != 1 || k < 2) return 1;

    long long arr[10];
    for (int i = 0; i < k; i++) {
        scanf("%lld", &arr[i]);
    }

    long long result_gcd = 0;
    long long result_lcm = 0;

    find_array_gcd_lcm(k, arr, &result_gcd, &result_lcm);

    printf("Array GCD: %lld | Array LCM: %lld\n", result_gcd, result_lcm);
    return 0;
}

Abrir en el compilador

Solución y explicación

Inicializa ambos acumuladores con el primer elemento y combina cada elemento posterior con ellos. Euclides reduce el segundo operando hasta cero.

Dividir por el MCD antes de multiplicar evita un producto intermedio innecesariamente grande. La garantía de rango del ejercicio sigue siendo necesaria; la fórmula no elimina todo riesgo de desbordamiento para entradas arbitrarias.

C pasa el valor de cada puntero; escribir en *out_gcd y *out_lcm modifica los objetos del llamador. Cada cálculo de MCD es logarítmico en el menor operando y la recursión usa una pila de profundidad logarítmica.

Código de la solución

#include <stdio.h>

// Recursive Euclidean algorithm
long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// Compute LCM preventing overflow by dividing before multiplying
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    return (a / gcd(a, b)) * b;
}

// Compute GCD and LCM for an array using pointers
void find_array_gcd_lcm(int k, long long arr[], long long *out_gcd, long long *out_lcm) {
    if (k <= 0) return;

    long long current_gcd = arr[0];
    long long current_lcm = arr[0];

    for (int i = 1; i < k; i++) {
        current_gcd = gcd(current_gcd, arr[i]);
        current_lcm = lcm(current_lcm, arr[i]);
    }

    *out_gcd = current_gcd;
    *out_lcm = current_lcm;
}

int main(void) {
    int k;
    if (scanf("%d", &k) != 1 || k < 2 || k > 10) return 1;

    long long arr[10];
    for (int i = 0; i < k; i++) {
        if (scanf("%lld", &arr[i]) != 1) return 1;
    }

    long long result_gcd = 0;
    long long result_lcm = 0;

    find_array_gcd_lcm(k, arr, &result_gcd, &result_lcm);

    printf("Array GCD: %lld | Array LCM: %lld\n", result_gcd, result_lcm);
    return 0;
}

Preguntas frecuentes

¿Por qué el código y la salida siguen en inglés?

Las palabras clave, los identificadores y los textos que verifican las pruebas se conservan para no cambiar el programa. Las explicaciones y los controles están traducidos.