Cod sursa(job #690254)

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

using namespace std;

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

	if(!b) 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 % d)
			printf("0 0\n");
		else
			printf("%ld %ld\n", X * (c / d), Y * (c / d));
		
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;

}