Pagini recente » Cod sursa (job #1938747) | Cod sursa (job #1977533) | Cod sursa (job #2181540) | Cod sursa (job #1176206) | Cod sursa (job #352469)
Cod sursa(job #352469)
#include <stdio.h>
#include <algorithm>
#define x first
#define y second
using namespace std;
pair<long long, long long> gcd_e(long long a, long long b)
{
pair<long long, long long> ret, temp;
if(b == 0)
{
return make_pair((long long)1, (long long)0);
}
temp = gcd_e(b, a % b);
ret.x = temp.y;
ret.y = temp.x - ret.x * (a / b);
return ret;
}
int main()
{
freopen("euclid3.in", "r", stdin);
freopen("euclid3.out", "w", stdout);
int t;
long long a, b, c, d;
pair<long long, long long> ret;
for(scanf("%d", &t); t; --t)
{
scanf("%lld %lld %lld", &a, &b, &c);
ret = gcd_e(a, b);
d = a * ret.x + b * ret.y;
if(c % d != 0)
{
printf("0 0\n");
}
else
{
ret.x *= c/d;
ret.y *= c/d;
while(ret.x > 2000000000 || ret.y < -2000000000)
{
ret.x -= b/d * c;
ret.y += a/d * c;
}
while(ret.x < -2000000000 || ret.y > 2000000000)
{
ret.x += b/d * c;
ret.y -= a/d * c;
}
printf("%lld %lld\n", ret.x, ret.y);
}
}
return 0;
}