Cod sursa(job #250314)

Utilizator willliIonel Bratianu willli Data 30 ianuarie 2009 16:52:05
Problema Algoritmul lui Euclid extins Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.88 kb
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000000

int euclid_extended(long int a, long int b, long int c, long int *x, long int *y)
{
	if (b == 0)
	{
		*x = 1;
		*y = 0;
		return a;
	}
	else 
	{
		long int d, x0, y0;		
		d = euclid_extended(b, a % b, c, &x0, &y0);
		//printf("a= %ld b = %ld c = = %ld x0 = = %ld y0 = %ld\n", a, b, c, x0, y0);
		*x = y0;
		*y = x0 - (a / b) * y0;
		return d;
	}
}

int main()
{
	long int a,b,t, i, c, x, y, d;
	FILE *fin, *fout;
	
	if ((fin = fopen("euclid3.in", "r")) == NULL)
	{
		printf("Eroare \n");
		exit(-1);
	}
	fscanf(fin, "%ld", &t);
	fout = fopen("euclid3.out", "w");
	for (i = 0; i < t; i++)
	{
		fscanf(fin,"%ld%ld%ld", &a, &b,&c);
		d = euclid_extended(a,b, c, &x, &y);
		x = x * (c /d);
		y = y * (c / d);
		if (a*x + b*y == c)
			fprintf(fout,"%ld %ld\n", x, y);
		else
			fprintf(fout,"0 0\n");
	}
	fclose(fin);
	fclose(fout);
	return 0;
}