Cod sursa(job #708790)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 7 martie 2012 10:49:50
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>

long K, i, a, b, c, x, y, r;

int euclid(long a, long b) {
	if (b == 0) {
		return a;
	}
	return euclid(b, a%b);
}

void euclidExtins(long a, long b, long &x, long &y) {
	long r, u1, v1, u2, v2, c;
	u1 = 1; v1 = 0;
	u2 = 0; v2 = 1;
	do {
		c = a/b;
		r = a%b;
		x = u1 - c * u2;
		y = v1 - c * v2;
		if (r != 0) {
			u1 = u2, u2 = x;
			v1 = v2, v2 = y;
			a = b;
			b = r;
		}
	} while (r != 0);
}

int main() {
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	
		scanf("%ld", &K);
		for (i = 0; i < K; ++i) {
			scanf("%ld %ld %ld", &a, &b, &c);
			r = euclid(a, b);
			euclidExtins(a, b, x, y);
			if (c % r == 0) {
				printf("%ld %ld\n", x*c/r, y*c/r);
			} else {
				printf("0 0\n");
			}
		}
	
	return 0;
}