Cod sursa(job #690256)

Utilizator michael9ufoStanescu Mihai michael9ufo Data 25 februarie 2012 14:06:57
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <fstream>

using namespace std;

long cmmdc(long a, long b, long &X, long &Y)
{

	if(!b){
		X = 1;
		Y = 0;
		return a;
	}
	long R, X0, Y0;
	
	R = cmmdc(b, a % b, X0, Y0);
	
	X = Y0;
	
	Y = X0 - (a / b) * Y0;
	
	return R;

}

int main()
{
	
	short T, i;
	
	long a, b, c;
	
	freopen("euclid3.in", "r", stdin);
	freopen("euclid3.out", "w", stdout);
	
	scanf("%hd", &T);
	
	for(i=1;i<=T;++i)
	{		
		scanf("%ld %ld %ld", &a, &b, &c);
		
		long X, Y, R;
		
		R = cmmdc(a, b, X, Y);
		
		if(c % R)
			printf("0 0\n");
		else
			printf("%ld %ld\n", X * (c / R), Y * (c / R));
		
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;

}