Cod sursa(job #596533)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 17 iunie 2011 17:59:34
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>

int Euclid3(int a,int b,int *x,int *y)
{
	int d;
	int c[100];
	int i=-1;
	int r;

	while(b!=0){
		r=a%b;
		c[++i]=a/b;
		a=b;
		b=r;
	}
	d=a;

	if(i>0){
		--i;
		*x = 1;
		*y = -c[i];
		--i;
		int aux;
	
		while(i>=0)
		{
			aux = *x;
			*x = *y;
			*y = aux -c[i]*(*y);
			--i;
		}
	}
	else if(i==0){
		*x=0;
		*y=1;
	}
	else if(i==-1){
		*x=1;
		*y=0;
	}
	return d;
}

int main(int argc, char* argv[])
{
	FILE *fpr,*fpw;
	int T;
	int a,b,c,d;
	int x,y;
	fpr = fopen("euclid3.in","r");
	fpw = fopen("euclid3.out","w");

	fscanf(fpr,"%d",&T);
	int i;
	for(i=0;i<T;i++)
	{
		fscanf(fpr,"%d %d %d",&a,&b,&c);
		d = Euclid3(a,b,&x,&y);
		if(x==0 && y==0)
			fprintf(fpw,"0 0\n");
		else{
			if(c%d == 0)
				fprintf(fpw,"%d %d\n",x*c/d,y*c/d);
			else
				fprintf(fpw,"0 0\n");
		}
	}

	fclose(fpr);
	fclose(fpw);
	return 0;
}