h2(#oz). 'Oz':problema/oz

 
Fie $v$ vectorul de $N$ numere care reprezinta solutia problemei. Initial consideram toate elementele vectorului $v$ ca fiind egale cu {$1$}. In momentul in care intalnim o pereche de forma ({$i j d$}), facem urmatoarele transformari:
 
* {$v{~i~}$} devine {$cmmmc(v{~i~}, d)$}
* {$v{~j~}$} devine {$cmmmc(v{~j~}, d)$},
 
unde prin {$cmmmc(a, b)$} se noteaza cel mai mic multiplu comun al numerelor $a$ si {$b$}.
Acest lucru garanteaza ca atat {$v{~i~}$} cat si {$v{~j~}$} se divid prin {$d$}, si ca toate relatiile anterioare sunt respectate. In plus, deoarece alegem cel mai mic multiplu comun, stim sigur ca solutia pe care o obtinem va fi minim posibila. Este insa posibil ca cele $M$ relatii date sa fie contradictorii. De exemplu, pentru {$N = 3$} si relatiile ({$1,2,3$}), ({$2,3,6$}) si ({$1,3,1$}) nu vom avea solutie, deoarece din primele doua relatii stim sigur ca atat {$v{~1~}$} cat si {$v{~3~}$} sunt divizibile cu 3, in timp ce ultima relatie cere ca cele doua numere sa fie prime intre ele. Pentru a verifica daca intr-adevar problema are solutie este suficient, dupa ce obtinem vectorul $v$ prin procedeul de mai sus, aplicand transformarile corespunzatoare tuturor celor $M$ relatii, sa testam pentru fiecare triplet ({$i j d$}) daca intr-adevar cel mai mare divizor comun dintre {$v{~i~}$} si {$v{~j~}$} este {$d$}, in caz contrar neexistand solutie.
Pentru a calcula {$cmmmc(a, b)$} se foloseste relatia {$cmmmc(a, b)$} = {$a * b / cmmdc(a, b)$}, iar {$cmmdc(a, b)$} se va calcula optim folosind 'Algoritmul lui Euclid':problema/euclid2.