Pagini recente » Cod sursa (job #491109) | Cod sursa (job #1208660) | Cod sursa (job #1522157) | Cod sursa (job #2457456) | Cod sursa (job #3295990)
#include <bits/stdc++.h>
using namespace std;
int euclid_extins(int a, int b, int& x1, int& y1) //algoritmul lui euclid extins pentru a afla x1 si y1 astfel incat a*x1+b*y1=(a, b)
{
if(b==0)
{
x1=1;
y1=0;
return a; //returnam cmmdc-ul numerelor
}
int x2, y2;
int d=euclid_extins(b, a%b, x2, y2);
x1=y2;
y1=x2-a/b*y2;
return d; //returnam cmmdc-ul numerelor
}
int main()
{
ifstream cin("euclid3.in");
ofstream cout("euclid3.out");
int t;
cin >> t;
while(t--)
{
int a, b, c;
cin >> a >> b >> c;
int x1, y1; //numerele pentru care a*x1+b*y1=(a, b), unde (a, b) este cmmdc-ul lui a si b
int d=euclid_extins(a, b, x1, y1); //cmmdc-ul lui a si b
if(c%d==0) //daca c este divizibil cu d, atunci exista o solutie pentru ecuatie
{
int factor=c/d; //factorul cu care se inmulteste toata ecuatia a*x1+b*y1=d
cout << factor*x1 << " " << factor*y1 << "\n";
}
else //daca nu, atunci nu exista nici-o solutie in numerele intregi
{
cout << 0 << " " << 0 << "\n";
}
}
return 0;
}