Cod sursa(job #231840)

Utilizator cotofanaCotofana Cristian cotofana Data 14 decembrie 2008 14:48:43
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <stdio.h>

void cmmdc(long a, long b, long *d, long *x, long *y)
{
	long x0, y0;
	if (!b)
	{
		*d=a;
		*x=1;
		*y=0;
	}
	else
	{
		cmmdc(b, a%b, d, &x0, &y0);
		*x=y0;
		*y=x0-(a/b)*y0;
	}
}

int main()
{
	long t, a, b, d, x, y, c;
	freopen("euclid3.in", "r", stdin);
	freopen("euclid3.out", "w", stdout);
	scanf("%ld\n", &t);
	for (; t; t--)
	{
		scanf("%ld %ld %ld\n", &a, &b, &c);
		if (a<b) cmmdc(b, a, &d, &y, &x);
		else cmmdc(a, b, &d, &x, &y);
		if (c%d==0) printf("%ld %ld\n", x*c/d, y*c/d);
		else printf("0 0\n");
	}
	return 0;
}