`std::gcd` în C++

Calculează cel mai mare divizor comun (gcd) și cel mai mic multiplu comun (lcm) a două numere întregi.

Sintaxă

constexpr std::common_type_t<M, N> gcd(M m, N n);
constexpr std::common_type_t<M, N> lcm(M m, N n);

Ce face `std::gcd`

std::gcd(a, b) returnează cel mai mare număr care îi divide pe amândoi; std::lcm(a, b) returnează cel mai mic număr divizibil cu amândoi. Ambele sunt în <numeric> și primesc doar tipuri întregi.

Semnul nu contează (se folosesc valorile absolute). gcd(0, n) este |n|, iar lcm(0, n) este 0. Pentru mai multe numere, combini cu std::accumulate sau std::reduce.

Parametri

Parametru	Descriere
`m, n`	Două numere întregi.

Ce returnează

Divizorul comun maxim, respectiv multiplul comun minim.

Exemple

Exemplul 1: Simplificarea unei fracții

#include <numeric>
#include <print>

int main() {
    int numarator = 84;
    int numitor = 126;

    int d = std::gcd(numarator, numitor);
    std::println("{}/{} = {}/{}", numarator, numitor, numarator / d, numitor / d);
}

Rezultat

84/126 = 2/3

Exemplul 2: Când pleacă autobuzele din nou împreună

Liniile pleacă la 12, 18 și 30 de minute; cel mai mic multiplu comun spune când coincid din nou.

#include <numeric>
#include <print>
#include <vector>

int main() {
    std::vector<int> intervale{12, 18, 30};

    int dupa = std::accumulate(intervale.begin(), intervale.end(), 1,
                               [](int a, int b) { return std::lcm(a, b); });
    std::println("Pleacă din nou împreună după {} de minute", dupa);
    std::println("gcd(-12, 18) = {}, gcd(0, 7) = {}", std::gcd(-12, 18), std::gcd(0, 7));
}