CMMMC-ul a două numere

Am învățat deja cum se calculează CMMDC (Cel Mai Mare Divizor Comun).

Acum vom învăța despre CMMMC - Cel Mai Mic Multiplu Comun.

Ce este un multiplu comun?

Un număr m este multiplu comun pentru a și b dacă:

• m % a == 0
• m % b == 0

Adică m se împarte exact atât la a, cât și la b.

Exemplu pentru 4 și 6:

• multiplii lui 4: 4, 8, 12, 16, 20, 24, ...
• multiplii lui 6: 6, 12, 18, 24, 30, ...
• multiplii comuni: 12, 24, 36, ...
• cel mai mic dintre ei este 12

Deci CMMMC(4, 6) = 12.

La ce ne ajută CMMMC?

• să aflăm peste câte zile se vor întâlni din nou două evenimente periodice;
• să aducem fracții la un numitor comun;
• să sincronizăm lucruri care se repetă la intervale diferite.

Soluția 1 (ineficientă): căutare pas cu pas

Ideea:

• pornim de la cel mai mare dintre a și b;
• verificăm dacă numărul curent se împarte exact la ambele;
• dacă da, acesta este CMMMC;
• dacă nu, creștem valoarea cu 1 și repetăm.

int a, b;
cin >> a >> b;

int m;
if (a > b) {
    m = a;
} else {
    m = b;
}

while (m % a != 0 || m % b != 0) {
    m++;
}

cout << m;

Input:
4 6

Output:
12

De ce este ineficientă?

Pentru numere mari, bucla poate face foarte mulți pași.

De exemplu, CMMMC(1, 1000000) = 1000000, dar CMMMC(7, 13) = 91. Nu știm dinainte câte verificări sunt necesare.

Soluția 2 (eficientă): formula cu CMMDC

Există o legătură foarte importantă între CMMDC și CMMMC:

CMMMC(a, b) = a * b / CMMDC(a, b)

Aceasta este formula pe care o folosim în practică.

De ce funcționează?

Să luăm a = 12 și b = 18:

• CMMDC(12, 18) = 6
• 12 * 18 = 216
• 216 / 6 = 36
• deci CMMMC(12, 18) = 36

Verificare: 36 / 12 = 3 (exact) și 36 / 18 = 2 (exact).

Codul complet

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;

    // Calculam CMMDC cu algoritmul lui Euclid
    int x = a, y = b;

    while (y != 0) {
        int r = x % y;
        x = y;
        y = r;
    }

    int cmmdc = x;
    int cmmmc = a * b / cmmdc;

    cout << cmmmc;

    return 0;
}

Input:
4 6

Output:
12

Explicație pas cu pas pentru 4 și 6

1. Calculăm CMMDC:
   • (4, 6) → r = 4 % 6 = 4 → (6, 4)
   • (6, 4) → r = 6 % 4 = 2 → (4, 2)
   • (4, 2) → r = 4 % 2 = 0 → (2, 0)
   • CMMDC = 2
2. Aplicăm formula:
   • CMMMC = 4 * 6 / 2 = 12

Atenție la depășire (overflow)

Dacă a și b sunt numere mari, produsul a * b poate depăși limita lui int.

Pentru a evita acest lucru, împărțim mai întâi:

int cmmmc = a / cmmdc * b;

În loc de a * b / cmmdc, scriem a / cmmdc * b.

Acest lucru funcționează pentru că a se divide exact la cmmdc, deci a / cmmdc este un număr întreg.

Mai multe exemple

Observații:

• dacă a și b sunt prime între ele (CMMDC = 1), atunci CMMMC = a * b;
• dacă a == b, atunci CMMMC = a;
• CMMMC este întotdeauna mai mare sau egal cu max(a, b).

Greșeli frecvente

1. Uitarea calculului CMMDC

CMMMC nu poate fi calculat eficient fără CMMDC. Formula a * b / CMMDC este esențială.

2. Modificarea valorilor originale

Algoritmul lui Euclid modifică variabilele a și b. Dacă avem nevoie de valorile inițiale pentru formulă, trebuie să le salvăm:

int x = a, y = b; // copii pentru Euclid

while (y != 0) {
    int r = x % y;
    x = y;
    y = r;
}

int cmmmc = a / x * b; // folosim a si b originale

3. Depășirea la a * b

Dacă scriem a * b / cmmdc, produsul poate depăși int (peste 2 miliarde).

Soluția: a / cmmdc * b.

Ce să reții

• CMMMC este cel mai mic număr care se divide exact la ambele numere.
• Formula eficientă: CMMMC(a, b) = a / CMMDC(a, b) * b.
• Trebuie calculat mai întâi CMMDC (cu algoritmul lui Euclid).
• Atenție la ordinea operațiilor: împarte mai întâi, apoi înmulțește.
• Salvează valorile originale ale lui a și b înainte de a calcula CMMDC.

Probleme

pbinfoCmmmc→

pbinfoCmmdc Cmmmc→