Cod sursa(job #572255)

Utilizator Rares95Rares Arnautu Rares95 Data 5 aprilie 2011 09:58:27
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
	
  # include <algorithm>
	using namespace std;
	
	int T, a, b, c, s, t;
	
	int euclid_extins (int a, int b, int &s, int &t) {
		int r, c, s1, s2, t1, t2;
		if ( !b ) {
			s = 1;
			t = 0;
			return a;
		}
		s1 = 1; t1 = 0; s2 = 0; t2 = 1;
		for ( r = a % b, c = a / b; r; ) {
			s = s1 - s2 * c; s1 = s2; s2 = s;
			t = t1 - t2 * c; t1 = t2; t2 = t;
			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, s, t );
			if ( c % d ) {
				printf ( "0 0\n" );
			}
			else {
				c /= d;
				printf ( "%d %d\n", s * c, t * c );
			}
		}
		
		return 0;
	}