Pagini recente » Cod sursa (job #1786868) | Cod sursa (job #1292351) | Cod sursa (job #1120604) | Cod sursa (job #2465853) | Cod sursa (job #2612302)
#include <fstream>
using namespace std;
ifstream cin("euclid3.in");
ofstream cout("euclid3.out");
///ax + by = d
///Ecuatia are solutii daca d este multiplu de cmmmdc(a,b)
///timp de executie --- complexitate log(max(a,b))
/*
a,b-coeficienti
ax + by = d
x = y0;
y = x0 - (a/b) * y0;
========
bx0 + (a%b)y0 = d -> x ,y
=======
(a%b)xa + ((a%b) % b) *yb = d -> x0,yo
=====
(a%b)% b * x2 + (a%b)%((a%b)%b)*y2 = d => x2 =
=====
x = 1
y = 0
*/
int cmmdc_ext(int a,int b,int &x,int &y){
if(b==0) {
x = 1;
y = 0;
return a;
}
int x0,y0,d;
d = cmmdc_ext(b,a%b,x0,y0);
x =y0;
y = x0-(a/b)*y0;
return d;
}
///a *x + b*y = d | *(c/d)
int main()
{
int a, b,c,x,y,n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin>>a>>b >> c;
int d = cmmdc_ext(a,b,x,y);
if(c % d == 0) {
cout << x * (c/d) << " " << y * (c/d) << "\n";///inmultesc
}
else
cout << 0 << " " << 0 << "\n";
}
return 0;
}