Revizia anterioară Revizia următoare
| 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 = d, cu coeficientii a, b si d. Pentru fiecare dintre aceste ecuatii se cere aflarea unei perechi de numere 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, d.
Date de iesire
Fisierul de iesire euclid3.out va contine T linii. Pe linia i se vor afla o pereche de numere x y care respecta ecuatia cu numarul i sau 0 0 in cazul in care ecuatia nu are solutie.
Restrictii
- 1 ≤ T ≤ 100
- -1 000 000 000 ≤ a ≤ b ≤ 1 000 000 000
- d diferit de 0
- Pentru toate ecuatiile pentru care exista solutie, va exista si o solutie cu ambele necunoscute aflate in intervalul -2 000 000 000, 2 000 000 000.
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.
O solutie de 100 de puncte, pe ideea din articolul de mai sus, o gasiti aici.
