Grade 10 · Subprograms (functions)Citește în română

GCD and LCM functions

Original: Funcție cmmdc și cmmmc

O(log n)C++1745 lines2 examples

The idea

The function cmmdc(a, b) applies Euclid's algorithm by division: while b is not 0, the pair (a, b) becomes (b, a % b). The function cmmmc(a, b) reuses the first one: lcm = a / cmmdc(a, b) * b (we divide first, so the product does not overflow the data type).

Original description (Romanian)

Funcția cmmdc(a, b) aplică algoritmul lui Euclid prin împărțiri: cât timp b nu este 0, perechea (a, b) devine (b, a % b). Funcția cmmmc(a, b) o refolosește pe prima: cmmmc = a / cmmdc(a, b) * b (împărțim întâi, ca produsul să nu depășească tipul de date).

Complexity
O(log(min(a, b)))
Grade
Grade 10 (Clasa a X-a)

Examples

Example 1

Input

12 18

Expected output

6 36
Example 2

Input

17 5

Expected output

1 85

The code

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

functie-cmmdc.cpp
/*
 * Titlu: Funcție cmmdc și cmmmc
 * Clasa: 10
 * Capitol: Subprograme (funcții)
 * Descriere: Funcția cmmdc(a, b) aplică algoritmul lui Euclid prin împărțiri:
 *            cât timp b nu este 0, perechea (a, b) devine (b, a % b). Funcția
 *            cmmmc(a, b) o refolosește pe prima: cmmmc = a / cmmdc(a, b) * b
 *            (împărțim întâi, ca produsul să nu depășească tipul de date).
 * Complexitate: O(log(min(a, b)))
 *
 * Exemplu
 * Intrare: 12 18
 * Ieșire: 6 36
 *
 * Exemplu
 * Intrare: 17 5
 * Ieșire: 1 85
 */
#include <iostream>
using namespace std;

long long cmmdc(long long a, long long b)
{
    while (b != 0)
    {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

long long cmmmc(long long a, long long b)
{
    return a / cmmdc(a, b) * b;
}

int main()
{
    long long a, b;
    cin >> a >> b;
    cout << cmmdc(a, b) << ' ' << cmmmc(a, b) << '\n';
    return 0;
}

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