Учебная версия на русском. Код и его вывод сохранены в исходном виде.

Рекурсивные функции: НОД и НОК массива

Объедините алгоритм Евклида с выходными параметрами через указатели.

Прочитайте K положительных целых. Реализуйте gcd(a, b) рекурсивно через gcd(b, a % b) с базовым случаем b == 0. Вычисляйте наименьшее общее кратное формулой (a / gcd(a, b)) * b.

Реализуйте find_array_gcd_lcm с параметрами k, arr, out_gcd и out_lcm. Последовательно объединяйте элементы массива в оба результата и запишите их через выходные указатели. Сохраните метки Array GCD: и Array LCM: без перевода.

Ввод

Первая строка: K. Вторая строка: K положительных целых через пробел.

Вывод

Array GCD: <НОД> | Array LCM: <НОК>

Ограничения

2 <= K <= 10
1 <= arr[i] <= 1 000 000
Итоговый НОК помещается в знаковый 64-битный long long.

Подсказки

При b == 0 верните a, иначе вызовите gcd(b, a % b).
При вычислении НОК выполняйте деление до умножения.

Код 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;
}

Открыть в компиляторе

Решение и объяснение

Инициализируйте оба накопителя первым элементом, затем объединяйте их с последующими. Алгоритм Евклида уменьшает второй операнд до нуля.

Деление на НОД перед умножением избегает лишнего большого промежуточного произведения. Гарантия диапазона из условия всё равно нужна: формула не исключает переполнение для любых данных.

C передаёт значения указателей; запись в *out_gcd и *out_lcm меняет объекты вызывающего кода. Каждый поиск НОД логарифмичен по меньшему операнду и использует логарифмическую глубину рекурсии.

Код решения

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

Частые вопросы

Почему код и вывод остаются на английском?

Ключевые слова, идентификаторы и строки, проверяемые тестами, сохранены, чтобы не менять программу. Объяснения и элементы управления переведены.