Multiplu
O rezolvare triviala ar fi generarea (prin metoda backtracking) in ordine crescatoare a tuturor numerelor formate doar din cifre de 0 si 1 si verificarea proprietatii de divizibilitate. In momentul in care am intalnit un numar care este multiplu si pentru A si pentru B afisam rezultatul si oprim executia programului.
Solutia optima are complexitatea O(A*B). Fie M cel mai mic multiplu comun pentru numerele A si B. Trebuie sa determinam cel mai mic numar natural format doar cu cifre de 0 si 1 si care este multiplu pentru M. Vom avea o coada in care vom introduce cele mai mici numere formate cu 0 si 1 care dau un anumit rest la impartirea cu M. Initial, in coada se va afla doar numarul 1. La un moment dat, daca ne aflam pe pozitia i in coada si pe aceasta pozitie se afla numarul X, tratam urmatoarele cazuri:
- adaugam cifra 0 la sfarsitul lui X. Daca nu exista nici un numar in coada care sa aiba restul (X*10) % M, atunci introducem X*10 in coada.
- adaugam cifra 1 la sfarsitul lui X. Daca nu exista nici un numar in coada care sa aiba restul (X*10+1) % M, atunci introducem X*10+1 in coada.
In momentul in care introducem in coada un numar care are restul 0 la impartirea cu M, il afisam si oprim executia programului. Se observa ca in coada vor fi introduse cel mult M numere, deoarece exista M resturi posibile la impartirea cu M. Cum M este cel mult A*B, complexitatea acestui algoritm este O(A*B).
Din motive de eficienta, in coada nu vor fi introduse numerele propriu-zis, ci doar resturile acestora la impartirea cu M. Pentru reconstituirea solutiei este necesara retinerea a doi vectori suplimentari up si cif, unde upi indica ultima pozitie de la care s-a plecat pentru a ajunge la pozitia i, iar cifi este ultima cifra (0 sau 1) a numarului de pe pozitia i in coada.
