Cod sursa(job #177942)

Utilizator amadaeusLucian Boca amadaeus Data 13 aprilie 2008 21:09:39
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <cstdio>

using namespace std;

int N;

int solve( int a, int b, int &x, int &y ) {
	int d, xx, yy;
	
	if( b == 0 ) {
		x = 1; y = 0;
		return a;
	}
	d = solve( b, a%b, x, y );
	xx = y;
	yy = x - y * (a/b);
	x = xx, y = yy;
	
	return d;
}

void cit() {
	int i, x, y, a, b, c, d;

	scanf( "%d", &N );

	for( i = 1; i <= N; i++ ) {
		scanf( "%d %d %d ", &a, &b, &c );
		d = solve( a, b, x, y );
		if( c % d )
			printf( "0 0\n" );
		else
			printf( "%d %d\n", x * (c/d), y * (c/d) );
	}
}

int main() {
	freopen( "euclid3.in", "r", stdin );
	freopen( "euclid3.out", "w", stdout );

	cit();

	return 0;
}