Pagini recente » Cod sursa (job #2381673) | Cod sursa (job #1114576) | Cod sursa (job #2814094) | Cod sursa (job #313910) | Cod sursa (job #2462397)
#include <fstream>
using namespace std;
int gcd_extins(int a, int b, int &x, int &y, int &d)
{/*Algoritmul rezolva ecuatia a*x + b*y = d, unde d este cmmdc(a,b)
Date de intrare: a,b coeficienti cunoscuti, numere intregi
Date de iesire: x,y necunoscutele ecuatiei
*/
if(b==0)
{/*primul apel*/
d = a;
x = 1;
y = 0;
}
else
{
/*necunoscutele apelului precedent*/
int x0=0, y0=0;
gcd_extins(b,a%b,x0,y0,d);
/*necunoscutele apelului curent, dependenta se demonstreaza prin calcul matematic*/
x = y0;
y = x0 - (a/b)*y0;
}
}
void solve()
{ifstream in("euclid3.in");
ofstream out("euclid3.out");
int nT;
in>>nT;
for(int i=0; i<nT; i++)
{
int a,b,c;
in>>a>>b>>c;
/*Se cere rezolvarea ecuatiei a*x + b*y = c, a,b,c,x,y sunt numere intregi.
Din algoritmul lui Euclid extins => a*x + b*y = (a,b) => ecuatia se poate rezolva <=> c este multiplu de (a,b)
*/
int x=0, y=0, d=0;
gcd_extins(a,b,x,y,d);
if(c%d==0)/*se poate rezolva*/
out<<(c/d)*x<<" "<<(c/d)*y<<'\n';
else
out<<0<<" "<<0<<'\n';
}
in.close();
out.close();
}
int main()
{
solve();
return 0;
}