Cod sursa(job #523413)

Utilizator Rares95Rares Arnautu Rares95 Data 17 ianuarie 2011 22:29:34
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<stdio.h>
int n,a,b,c,d,e,i,x,y;

int euex(int a, int b, int &x, int &y)
{	int r,q,x1,x2,y1,y2;
	if(!b) {x=1; y=0; return a;}
	x1=1; x2=0; y1=0; y2=1; x=x2; y=y2;
	r=a%b; q=a/b;
	while(r)
	{	x=x1-x2*q; x1=x2; x2=x;
		y=y1-y2*q; y1=y2; y2=y;
		a=b; b=r; r=a%b; q=a/b;
	}
	return b;
}

int main()
{	FILE *fin, *fout;
	fin = fopen ("euclid3.in", "r");
	fout = fopen ("euclid3.out", "w");
	
	fscanf (fin,"%d",&n);
	for(;n;--n)
	{	fscanf (fin,"%d%d%d",&a,&b,&c);
		d=euex(a,b,x,y);
		if(c%d) fprintf (fout,"%s","0 0\n");
		else {c/=d; fprintf (fout,"%d%s%d%s",c*x," ",c*y,"\n");}
	}
	fclose(fout); return 0;
}