Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-02-26 14:34:01.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:euclid3.in, euclid3.outSursăad-hoc
AutorArhiva EducationalaAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.025 secLimită de memorie4608 kbytes
Scorul tăuN/ADificultateN/A

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.ineuclid3.out
3
24 15 147
24 16 104
2 4 5
33 -43
33 -43
0 0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

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.