Cod sursa(job #673395)

Utilizator marius135Dumitran Adrian Marius marius135 Data 4 februarie 2012 13:33:56
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
//Infoarena Arhiva Educationala euclid extins
//Marius Dumitran Februarie 2012
//

#include <stdio.h>

	
 int euclid_extins(int a, int b, int &x, int &y)
{
    if (b == 0) {
        x = 1;
        y = 0;
		return a;
	}
    int x0, y0;
    int d = euclid_extins(b, a % b, x0, y0);
    x = y0;
    y = x0 - (a / b) * y0;
	return d;
    
}

int main() {

	int N;
	freopen ("euclid3.in", "r", stdin);
	freopen ("euclid3.out", "w", stdout);
	scanf ("%d ", &N);
	for (int ii = 1; ii <= N; ++ii) {
		int A, B, C, X, Y;
		scanf ("%d %d %d", &A, &B, &C);
		
		int D = euclid_extins (A, B, X, Y);
		if( C % D )
			printf("0 0\n");
		else printf ("%d %d\n", X * (C/D), Y * (C/D));
	}
	
	
	return 0;
}