Pagini recente » Cod sursa (job #1997839) | Cod sursa (job #1150438) | Cod sursa (job #647780) | Cod sursa (job #1615170) | Cod sursa (job #1723602)
#include <cstdio>
using namespace std;
void extended_euclid(long long A,long long B, long long *C, long long *X, long long *Y){
if(B == 0)
{
*X = 1;
*Y = 0;
*C = A;
return;
}
long long newX,newY;
extended_euclid(B,A%B,C,&newX,&newY); /// newX* B + newY * (A - [A/B]*B) = A * X + B * Y
*X = newY;
*Y = newX - A/B*newY;
}
int main()
{
freopen("euclid3.in","r",stdin);
freopen("euclid3.out","w",stdout);
int N;
scanf("%d",&N);
long long A,B,C,D;
for(int i = 1; i <= N; ++i)
{
scanf("%lld%lld%lld",&A,&B,&D);
long long X,Y;
extended_euclid(A,B,&C,&X,&Y);
if(D % C != 0)
printf("0 0\n");
else
printf("%lld %lld\n",X * D/C, Y * D/C);
}
return 0;
}