Pagini recente » Cod sursa (job #1661783) | Cod sursa (job #2101559) | Cod sursa (job #3243377) | Cod sursa (job #782467) | Cod sursa (job #627032)
Cod sursa(job #627032)
#include <cstdio>
#define abs(a) ( (a) < 0 ? (-a) : (a) )
using namespace std;
int cmmdc(int a,int b)
{
if (b == 0) return a;
return cmmdc(b, a % b);
}
int c;
void diofant(int a, int b, int &x, int &y)
{
if (a == 1 && b == 1) {x = c; y = 0;}
else {
int x1, y1;
if (b > a) {
diofant (a, b-a, x1, y1);
x = x1 - y1;
y = y1;
}
else {
diofant (b, a-b, x1, y1);
x = y1;
y = x1 - y1;
}
}
}
int main()
{
freopen("euclid3.in", "r", stdin);
freopen("euclid3.out", "w", stdout);
int T,i;
scanf("%d", &T);
for (i = 0; i < T; i++)
{
int a, b;
scanf("%d %d %d", &a, &b, &c);
int d = cmmdc(a, cmmdc(b, c));
a /= d;
b /= d;
c /= d;
int x, y;
if (cmmdc(a,b) != 1) printf("0 0\n");
else
{
if(abs(a) < abs(b)) diofant(abs(b), abs(a), y, x);
else diofant(abs(a), abs(b), x, y);
if(a < 0) x *= -1;
if(b < 0) y *= -1;
printf("%d %d\n", x, y);
}
}
return 0;
}