Pagini recente » Cod sursa (job #592815) | Cod sursa (job #1848702) | Cod sursa (job #2716367) | Cod sursa (job #838975) | Cod sursa (job #1232208)
/*
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.
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.
*/
#include <fstream>
#include <iostream>
using namespace std;
int t,a,b,c,d,x,y; //c<>0 daca nu la impartire ar fi dat eroare
void euclid_extins(int a, int b, int &d, int &x, int &y)
{
if (b==0)
{
d = a;
x = 1;
y = 0;
}
else
{
int x0, y0;
euclid_extins(b, a % b, d, x0, y0);
x = y0;
y = x0 - (a / b) * y0;
}
}
void citire()
{
int i;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
f>>t;
for (i=1; i<=t; i++)
{
f>>a>>b>>c;
euclid_extins(a,b,d,x,y);
if(c % d == 0)
g<<x * (c / d)<<" "<<y * (c / d)<<"\n";
else
g<<"0 0\n";
}
f.close();
g.close();
}
int main()
{
citire();
return 0;
}