Edição didática em português. O código e suas saídas preservam o original.

Funções recursivas: MDC e MMC de um array

Combine o algoritmo de Euclides com parâmetros de saída por ponteiros.

Leia K inteiros positivos. Implemente gcd(a, b) recursivamente com gcd(b, a % b) e o caso base b == 0. Calcule o mínimo múltiplo comum com (a / gcd(a, b)) * b.

Implemente find_array_gcd_lcm com os parâmetros k, arr, out_gcd e out_lcm. Percorra o array acumulando os dois resultados e escreva-os pelos ponteiros de saída. Imprima os rótulos Array GCD: e Array LCM: sem traduzi-los.

Entrada

Primeira linha: K. Segunda linha: K inteiros positivos separados por espaços.

Saída

Array GCD: <mdc> | Array LCM: <mmc>

Restrições

2 <= K <= 10
1 <= arr[i] <= 1.000.000
O MMC final cabe em um long long com sinal de 64 bits.

Dicas

Quando b == 0, retorne a; caso contrário, chame gcd(b, a % b).
Divida antes de multiplicar ao calcular o MMC.

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 no compilador

Solução e explicação

Inicialize os dois acumuladores com o primeiro elemento e combine cada elemento seguinte com eles. Euclides reduz o segundo operando até zero.

Dividir pelo MDC antes de multiplicar evita um produto intermediário desnecessariamente grande. A garantia de faixa do exercício continua necessária; a fórmula não elimina todo risco de estouro para entradas arbitrárias.

C passa o valor de cada ponteiro; escrever em *out_gcd e *out_lcm modifica os objetos do chamador. Cada cálculo de MDC é logarítmico no menor operando e a recursão usa uma pilha de profundidade logarítmica.

Código da solução

#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;
}

Perguntas frequentes

Por que o código e a saída continuam em inglês?

Palavras-chave, identificadores e textos verificados pelos testes são preservados para não alterar o programa. As explicações e os controles estão traduzidos.