Cod sursa(job #208773)

Utilizator andrei.12Andrei Parvu andrei.12 Data 18 septembrie 2008 13:18:10
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<stdio.h>

int teste, a, b, c, x, y, d;

void euclid(int a, int b, int &x, int &y, int &d){
	if (!b){
		d = a;
		x = 1;
		y = 0;
		
		return ;
	}
	
	int xx, yy, q = a / b;
	euclid(b, a%b, xx, yy, d);
	
	x = yy;
	y = xx-yy*q;
}
int gcd(int a, int b){
	if (!b)
		return a;
	return gcd(b, a%b);
}
int main()
{
	freopen("euclid3.in", "rt", stdin);
	freopen("euclid3.out", "wt", stdout);
	
	scanf("%d", &teste);
	while (teste --){
		scanf("%d%d%d", &a, &b, &c);
		
		d = gcd(a, b); x = 0, y = 0;
		euclid(a, b, x, y, d);
		
		if (c % d != 0)
			printf("0 0\n");
		else
			printf("%d %d\n", c/d*x, c/d*y);
	}
	
	return 0;
}