| Fişierul intrare/ieşire: | euclid3.in, euclid3.out | Sursă | ad-hoc |
| Autor | Arhiva Educationala | Adăugată de |  Bogdan-Cristian Tataroiu •bogdan2412 |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 4608 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Algoritmul lui Euclid extins
Cerinta
Se dau T ecuatii de forma a * x + b * y = c, cu coeficientii a, b si c. Pentru fiecare dintre aceste ecuatii se cere aflarea unei perechi de numere intregi x y care sa satisfaca ecuatia, in cazul in care o astfel de pereche exista.
Date de intrare
Fisierul de intrare euclid3.in contine pe prima linie numarul T de teste. Urmatoarele T linii contin fiecare cate 3 numere intregi a, b, c.
Date de iesire
Fisierul de iesire euclid3.out va contine T linii. Pe linia i se va afla o pereche de numere intregi x y care respecta ecuatia cu numarul i sau 0 0 in cazul in care ecuatia respectiva nu are solutie.
Restrictii
- 1 ≤ T ≤ 100
- -1 000 000 000 ≤ a ≤ b ≤ 1 000 000 000
- -2 000 000 000 ≤ c ≤ 2 000 000 000, c diferit de 0.
- In cazul in care exista mai multe solutii pentru o ecuatie, se poate afisa oricare solutie pentru care necunoscutele nu depasesc in valoare absoluta 2 000 000 000. Pentru toate ecuatiile pentru care exista solutie, va exista si o solutie cu ambele necunoscute aflate in acest interval.
Exemplu
| euclid3.in | euclid3.out |
|---|---|
| 3 24 15 147 24 16 104 2 4 5 | 33 -43 33 -43 0 0 |
Indicatii de rezolvare
Ecuatiile pot fi rezolvate cu ajutorul algoritmului lui Euclid extins, prezentat in acest articol de pe infoarena. Astfel se poate determina perechea (x y) care satisface relatia a * x + b * y = d, unde d este cmmmdc(a, b). In cazul in care c nu se divide cu d ecuatia nu poate fi rezolvata in multimea numerelor intregi, in caz contrar se inmulteste intreaga ecuatie cu c / d.
O solutie de 100 de puncte, pe ideea de mai sus, o gasiti aici.
Ca o completare: Pentru fiecare ecuatie exista o infinitate de solutii. Avand dat a * x + b * y = c, se observa ca toate solutiile de forma (x + k * b/d, y - k * a/d), cu k intreg respecta ecuatia.
Ecuatia devine a * (x + k * b/d) + b * (y - k * a/d) = c. Desfacand parantezele: a * x + k * a * b / d + b * y - k * a * b / d = a * x + b * y. Solutiile noi sunt la randul lor intregi, a si b fiind divizibile cu d.
