Pagini recente » Cod sursa (job #3191933) | Cod sursa (job #478096) | Cod sursa (job #997003) | Cod sursa (job #3236593) | Cod sursa (job #2388617)
#include <bits/stdc++.h>
using namespace std;
long long i, n, X1, X2, Y1, Y2, x, y, rest1, rest2, rest, d, val, cat;
int cmmdc(int a, int b)
{
int d = a, i = b, r = d % i;
while(r != 0)
{
d = i;
i = r;
r = d % i;
}
return i;
}
int main()
{
ifstream f("euclid3.in");
ofstream g("euclid3.out");
f >> n;
for(i = 1; i <= n; i ++)
{
f >> rest1 >> rest2 >> d;
val = cmmdc(rest1, rest2);
X1 = 1;
X2 = 0;
Y1 = 0;
Y2 = 1;
if(d % val != 0)
{
g << "0 0" << "\n";
continue;
}
while(rest1 % rest2 != 0)
{
cat = rest1 / rest2;
rest = rest1 % rest2;
rest1 = rest2;
rest2 = rest;
x = X1 - cat * X2;
y = Y1 - cat * Y2;
X1 = X2;
X2 = x;
Y1 = Y2;
Y2 = y;
}
g << X2 * (d / val) << " " << Y2 * (d / val) << "\n";
}
return 0;
}