Cod sursa(job #550495)

Utilizator sebii_cSebastian Claici sebii_c Data 9 martie 2011 17:39:29
Problema Algoritmul lui Euclid extins Scor 30
Compilator c Status done
Runda Arhiva educationala Marime 0.63 kb
#include <stdio.h>

long x, y;

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

int main(argc, argv)
int argc;
char *argv[];
{
	FILE *fin = fopen("euclid3.in", "r");
	FILE *fout = fopen("euclid3.out", "w");
	long T, d, i;
	long a, b, c;
	fscanf(fin, "%ld", &T);
	for (i=0; i<T; ++i) {
		fscanf(fin, "%ld %ld %ld", &a, &b, &c);
		d = euclid_extins(a, b, &x, &y);
		if (c%d == 0)
			fprintf(fout, "%ld %ld\n", x*(c/d), y*(c/d));
		else fprintf(fout, "0 0");
	}
	fclose(fin);
	fclose(fout);
	return 0;
}