CMMDC al elementelor unui vector în C++

CMMDC înseamnă cel mai mare divizor comun. Pentru 18, 30 și 42, el este 6: toate cele trei valori se împart exact la 6 și nu există un divizor comun mai mare. Nu trebuie să enumerăm divizorii fiecărui element.

Reducem problema la două numere

Calculăm mai întâi CMMDC(18,30)=6, apoi CMMDC(6,42)=6. Un număr divide toate valorile procesate exact atunci când divide CMMDC-ul lor. De aceea rezultatul parțial este suficient pentru a continua cu următoarea valoare.

Pentru două numere folosim algoritmul lui Euclid: înlocuim perechea (a,b) cu (b,a%b), până când b devine zero. Restul % este ce rămâne după împărțirea întreagă. Pentru (18,30), perechile devin (30,18), (18,12), (12,6), (6,0); răspunsul este 6.

Citim 1≤n≤1000 și n numere naturale de cel mult 10^9, dintre care cel puțin unul este nenul. Afișăm CMMDC-ul tuturor. Convenția CMMDC(0,x)=x pentru x pozitiv permite inițializarea cu 0. Perechea (0,0) intermediară întoarce 0, dar condiția asupra intrării garantează un rezultat final pozitiv.

Pentru 18,30,42, pornim cu CMMDC zero. Rezultatele parțiale după fiecare valoare sunt 18,6,6.Mărește schema ↗

Varianta cu tablou clasic

#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;
}
int main() {
    int n; cin >> n;
    long long a[1000];
    for(int i=0;i<n;++i) cin >> a[i];
    long long g=0;
    for(int i=0;i<n;++i) g=cmmdc(g,a[i]);
    cout << g << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#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;
}
int main() {
    int n; cin >> n;
    vector<long long> a(n);
    for(int i=0;i<n;++i) cin >> a[i];
    long long g=0;
    for(int i=0;i<n;++i) g=cmmdc(g,a[i]);
    cout << g << '\n';
}

Ce păstrăm după fiecare pas

Variabila g reprezintă divizorul comun maxim al prefixului deja procesat, adică al primelor elemente citite până la acel punct. Un zero ulterior nu îl schimbă. Dacă g ajunge la 1, rezultatul final va fi 1, deoarece adăugarea unei condiții de divizibilitate nu poate mări CMMDC-ul.

Nu apelăm funcția cu numere negative: aceasta este limita declarată a problemei. Dacă extinzi domeniul, stabilește cum obții valorile absolute și ce tip poate reprezenta modulul celei mai mici valori negative.

Pentru limita maximă V a valorilor, Euclid are O(log V) pași în cel mai rău caz, iar repetarea pentru n elemente are O(n log V) timp. Tabloul ocupă O(n) memorie, starea calculului doar O(1). Se poate calcula direct la citire când nu mai ai nevoie de date ulterior.

Exersează

Vectorii 18 30 42, 0 0 12 și 8 9 0 dau 6, 12 și 1. Pentru un singur element pozitiv, rezultatul este acel element. Verifică aceste cazuri în ambele reprezentări, fără să folosești zero ca semn că intrarea este invalidă.

Reia algoritmul lui Euclid, parcurgerea unui vector și parametrii funcțiilor.

Întrebări frecvente

Ce înseamnă CMMDC al elementelor unui vector?

Este cel mai mare divizor comun al tuturor valorilor. Pentru 18, 30 și 42 este 6. Îl calculezi combinând succesiv rezultatul parțial cu următorul element prin algoritmul lui Euclid.

Cum influențează zero calculul CMMDC?

Pentru a pozitiv, CMMDC(a,0)=a. Un zero nu schimbă rezultatul parțial pozitiv. Cazul în care toate valorile sunt zero trebuie tratat conform convenției explicite a problemei.

Pot opri actualizările când CMMDC ajunge la 1?

Da, rezultatul nu mai poate deveni alt număr pozitiv prin adăugarea de elemente. Dacă mai există date obligatorii în flux, trebuie totuși să le citești conform formatului intrării.