Cod sursa(job #211492)

Utilizator vlad_popaVlad Popa vlad_popa Data 2 octombrie 2008 17:02:42
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include <cstdio>

inline int gcd (int a, int b, int &x, int &y){
	if (!b){
		x = 1;
		y = 0;
		return a;
	}

	int x0, y0, d;
	d = gcd (b, a % b, x0, y0);
	x = y0;
	y = x0 - (a / b) * y0;

	return d;
}

int main (){
	freopen ("euclid3.in", "r", stdin);
	freopen ("euclid3.out", "w", stdout);
    
	int T;
    for (scanf ("%d\n", &T); T; -- T){
		int A, B, C;
		scanf ("%d %d %d", &A, &B, &C);

		int D, X, Y;
		D = gcd (A, B, X, Y);
            
		if (C % D) printf ("0 0\n");
		else printf ("%d %d\n", X * (C / D), Y * (C / D));
	}

	return 0;
}