Cod sursa(job #572667)

Utilizator Rares95Rares Arnautu Rares95 Data 5 aprilie 2011 15:28:22
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
	
  # include <cstdio>
	using namespace std;
	
	int T, a, b, c, x, y;
	
	int euclid_extins ( int a, int b, int &x, int &y ) {
		
		int r, c, x1, x2, y1, y2;
		
		if ( !b ) {
			x = 1; y = 0;
			return a;
		}
		x1 = 1; y1 = 0; x = x2 = 0; y = y2 = 1;
		r = a % b; c = a / b;
		while ( r ) {
			x = x1 - x2 * c; x1 = x2; x2 = x;
			y = y1 - y2 * c; y1 = y2; y2 = y;
			a = b; b = r; r = a % b; c = a / b;
		}
		
		return b;
	}
	
	int main () {
		
		freopen ( "euclid3.in", "rt", stdin );
		freopen ( "euclid3.out", "wt", stdout );
		
		scanf ( " %d ", &T );
		for ( ; T; --T ) {
			
			scanf ( " %d %d %d ", &a, &b, &c );
			
			int d = euclid_extins ( a, b, x, y );
			
			if ( c % d ) printf ( "%s", "0 0\n" );
			else printf ( "%d %d\n", x * ( c / d ), y * ( c / d ) );
			
		}
		
		return 0;
		
	}