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:
- vi devine cmmmc(vi, d)
- vj devine cmmmc(vj, d),
unde prin cmmmc(a, b) se noteaza cel mai mic multiplu comun al numerelor a si b.
Acest lucru garanteaza ca atat vi cat si vj 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 v1 cat si v3 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 vi si vj 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.
