Pagini recente » Cod sursa (job #981777) | Cod sursa (job #2591184) | Cod sursa (job #1933792) | Cod sursa (job #1005021) | Cod sursa (job #1494843)
///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;
}