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

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content