h2. 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.

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 $x y$ care sa satisfaca ecuatia, in cazul in care o astfel de pereche exista.

h2. Date de intrare

h2. 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.

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.

h2. Restrictii

h3. Indicatii de rezolvare

Ecuatiile pot fi rezolvate cu ajutorul algoritmului lui Euclid extins, prezentat in acest "articol":algoritmul-lui-euclid 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$.
 

Ecuatiile pot fi rezolvate cu ajutorul algoritmului lui euclid extins, prezentat in acest "articol":algoritmul-lui-euclid de pe infoarena.

O solutie de 100 de puncte, pe ideea din articolul de mai sus, o gasiti "aici":job_detail/143208?action=view-source.
== include(page="template/taskfooter" task_id="euclid3") ==