Cod sursa(job #154215)

Utilizator zobicaMarin Marin zobica Data 10 martie 2008 23:50:59
Problema Algoritmul lui Euclid extins Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>


long cmmdc_extins(long a, long b, long &x, long &y) {
	long x0 = 0, y0 = 1;
	while (b) {
		long r = a % b, q = a / b;
		a = b;
		b = r;      
		long aux = x0;
		x0 = x - q * x0;
		x = aux;
		aux = y0;
		y0 = y - q * y0;
		y = aux;
	}
	return a;
}

int main() {
    freopen("euclid3.in", "r",stdin);
	freopen("euclid3.out", "w",stdout);
	long T;
    scanf("%ld", &T);
	for (long i = 0; i < T; i ++) {
		long a, b, d, c;    
		scanf("%ld %ld %ld", &a, &b, &c);
		long x = 1, y = 0;
		d = cmmdc_extins(a, b, x, y);
		if (c % d) {
			printf("0 0 0\n");
			continue;
		}
		x *= c/d;
		y *= c/d;
		printf("%ld %ld\n", x, y);
	}
	
    
    
    fclose(stdin);
	fclose(stdout);

    return 0;
}