euclid3

Euclid3

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

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.

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

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

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

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.

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

* $-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.

h2. Exemplu

0 0
|

h3. Indicatii de rezolvare

h2. Indicatii de rezolvare

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.

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$.
 
O solutie de 100 de puncte, pe ideea de mai sus, o gasiti "aici":job_detail/143238?action=view-source.
 
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$.

== include(page="template/taskfooter" task_id="euclid3") ==

2761