Pagini recente » Cod sursa (job #1536263) | Cod sursa (job #1629488) | Cod sursa (job #1025412) | Cod sursa (job #153066) | Cod sursa (job #1494842)
///Solutie explicata de marele matematician Tudor Bonifate
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll T , a , b , c , cmmdc;
ll x0 , x1 , y0 , y1 , x , y , r;
ll gcd(ll a , ll b)
{
ll r = a % b;
while (r)
{
a = b;
b = r;
r = a % b;
}
return b;
}
int main()
{
freopen("euclid3.in","r",stdin);
freopen("euclid3.out","w",stdout);
for (scanf("%lld", &T); T; --T)
{
scanf("%lld %lld %lld", &a, &b, &c);
cmmdc = gcd(a , b);
if (c % cmmdc)
{
printf("0 0\n");
continue;
}
x0 = 1; x1 = 0; y0 = 0; y1 = 1;
r = a % b;
while (r)
{
x = x0 - (a / b) * x1; x0 = x1; x1 = x;
y = y0 - (a / b) * y1; y0 = y1; y1 = y;
a = b; b = r; r = a % b;
}
printf("%lld %lld\n", x * c / cmmdc , y * c / cmmdc);
}
return 0;
}