Pagini recente » Cod sursa (job #1947689) | Cod sursa (job #1971835) | Cod sursa (job #2192471) | Cod sursa (job #1114024) | Cod sursa (job #1494851)
///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)
{
if (!b) return 0;
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);
if (!a && !b) {printf("0 0\n"); continue;}
cmmdc = gcd(a , b);
if (!a && b == c) {printf("0 1\n"); continue;}
if (a == c && !b) {printf("1 0\n"); continue;}
if (!cmmdc || c % cmmdc)
{
printf("0 0\n");
continue;
}
X0 = 1; X1 = 0; Y0 = 0; Y1 = 1; x = X1; y = Y1;
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;
}