Grade 9 · Number sequences read one at a timeCitește în română

GCD of several numbers

Original: Cmmdc-ul mai multor numere

O(n log n)C++1739 lines1 example

The idea

gcd(a, b, c) = gcd(gcd(a, b), c). We keep in rez the GCD of the numbers read so far and combine it, with Euclid's algorithm, with every new number. We start with rez = 0, because gcd(0, x) = x.

Original description (Romanian)

cmmdc(a, b, c) = cmmdc(cmmdc(a, b), c). Păstrăm în rez cmmdc-ul numerelor citite până acum și îl combinăm, cu algoritmul lui Euclid, cu fiecare număr nou. Pornim cu rez = 0, pentru că cmmdc(0, x) = x.

Complexity
O(n · log M), where M is the maximum value
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

4
12 18 30 42

Expected output

6

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

cmmdc-al-mai-multor-numere.cpp
/*
 * Titlu: Cmmdc-ul mai multor numere
 * Clasa: 9
 * Capitol: Șiruri de numere citite pe rând
 * Descriere: cmmdc(a, b, c) = cmmdc(cmmdc(a, b), c). Păstrăm în rez cmmdc-ul
 *            numerelor citite până acum și îl combinăm, cu algoritmul lui Euclid,
 *            cu fiecare număr nou. Pornim cu rez = 0, pentru că cmmdc(0, x) = x.
 * Complexitate: O(n · log M), unde M este valoarea maximă
 *
 * Exemplu
 * Intrare:
 * 4
 * 12 18 30 42
 * Ieșire: 6
 */
#include <iostream>
using namespace std;

int main()
{
    int n;
    long long x, rez = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        long long a = rez, b = x;
        while (b != 0)
        {
            long long r = a % b;
            a = b;
            b = r;
        }
        rez = a;
    }
    cout << rez << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.