Pagini recente » Cod sursa (job #1729777) | Cod sursa (job #1159264) | Cod sursa (job #1092933) | Cod sursa (job #509203) | Cod sursa (job #933078)
Cod sursa(job #933078)
#include <fstream>
#include <iostream>
using namespace std;
ifstream f("euclid3.in"); ofstream g("euclid3.out");
int a, b, d, x, y, c, n;
/**
* a and b are the numbers for gcd (a, b)
* d is the greatest common divisor
* x and y are a pair of numbers such that a*x + b*y = d
*
* For Base Case (where a = d) we have trivial answer a*1 + b*0 = d
* For Step we solve the following pair of equations
* a*x + b*y = d
* b*x + (a%b)*y = d
*
* Common factor by a and b, then choose trivial sollutions.
**/
void gcd (int a, int b, int &d, int &x, int &y){
if (b==0) {
d = a;
x=1; y=0;
}
else {
int x0, y0;
gcd (b, a%b, d, x0, y0 );
x = y0;
y = x0 - (a/b)*y0;
}
}
int main(){
f>>n;
while (n--){
f>>a>>b>>c;
gcd(a, b, d, x, y);
if (c%d) g<<"0 0\n";
else g<<x*(c/d)<<' '<<y*(c/d)<<"\n";
}
}