Cod sursa(job #208771)

Utilizator andrei.12Andrei Parvu andrei.12 Data 18 septembrie 2008 13:14:45
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 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);
		euclid(a, b, x, y, d);
		
		if (c % d != 0){
			printf("0 0\n");
			continue;
		}
		else
			printf("%d %d\n", x*c/d, y*c/d);
	}
	
	return 0;
}